Shortest path

Time Limit: 5000/1000 MS (Java/ Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 42695 Accepted Submission(s): 18706

Problem Description

In the annual school competition, all students who enter the final will get a very beautiful t-shirt. But every time our staff transports hundreds of pieces of clothes from the store back to the arena, it is very tiring! So now they want to find the shortest route from the store to the arena, can you help them?

the

input

The input includes multiple sets of data. The first line of each set of data is two integers N, M (N<=100, M<=10000), N indicates how many intersections there are on the streets of Chengdu, the intersection marked with 1 is the location of the store, and the intersection marked with N is the location of the venue, and M means that there are several roads in Chengdu. N=M=0 indicates the end of input. Next M lines, each line includes 3 integers A, B, C (1<=A, B<=N, 1<=C<=1000), indicating that there is a road between intersection A and intersection B, we It takes C minutes for the workers to walk this way.

Input guarantees that there is at least one route from the store to the arena.

the

output

For each set of inputs, output a row representing the shortest time it takes for a worker to walk from the store to the arena

the

Sample Input

the

Sample Output

the

source

UESTC 6th Programming Contest Online

the

//The basic template question of the shortest path, the reference code is as follows:

dijkstra

#include
 #include 
 #define INF 0x3f3f3f3f
 using namespace std;
 int cost[100][101];
 int d[110];
 bool used[110];
 int n,m;
 void dijkstra(int s)
 {
    for(int i=1;i<=n;i++)
      { d[i]=INF;
        used[i]=false;
      }
 d[s]=0;
   while(true)
     {
     int v=-1;
     for(int u=1;u<=n;u++)
     if(!used[u]&&(v==-1||d[u]<d[v]))
     v=u;
         if(v==-1)break;
         used[v]=true;
         for(int u=1;u<=n;u++)
          d[u]=min(d[u],d[v]+cost[v][u]);
     }
 }
 int main()
 {
 while(scanf("%d%d",&n,&m),n!=0&&m!=0)
 {
 int a,b,c;
 for(int i=1;i<=n;i++)
 for(int j=1;j<=n;j++)
 cost[i][j]=INF;
 for(int i=1;i<=m;i++)
 {
 scanf("%d%d%d",&a,&b,&c);
 cost[a][b]=c;
 cost[b][a]=c;
 }
 dijkstra(1);
 printf("%d\n",d[n]);
 }
 return 0;
 	
 }

SPFA algorithm

#include
 #include 
 #include 
 #include 
 using namespace std;
 #define maxn 1010
 #define maxm 20010
 #define INF 0x3f3f3f3f
 int n,m;
 int head[10010];
 int d[10010];
 int vis[10010];
 int cnt;
 struct s
 {
 int u,v,w,next;
 }edge[10010];
 void add(int u,int v,int w)
 {
   edge[cnt].u=u;
   edge[cnt].v=v;
   edge[cnt].w=w;
   edge[cnt].next=head[u];
   head[u]=cnt++;
 }
 void init()
 { cnt=0;
 memset(head,-1,sizeof(head));
 }
 void SPFA(int s)
 {
 queueq;
 memset(vis,0,sizeof(vis));
 memset(d,INF,sizeof(d));
 q. push(s);
 d[s]=0;
 vis[s]=1;
 while(!q.empty())
 {
 int u=q. front();
 q. pop();
 vis[u]=0;
 for(int i=head[u];i!=-1;i=edge[i].next)
 {
 int v=edge[i].v;
 if(d[v]>d[u]+edge[i].w)
 {d[v]=d[u]+edge[i].w;
 if(!vis[v])
 {
 vis[v]=1;
 q. push(v);
 }
 }
 // printf("%d\n",d[N]);
 }
 		
 		
 }
 printf("%d\n",d[n]);
 }
 void getmp()
 {
 int a,b,c;
 while(m--)
 {
 scanf("%d%d%d",&a,&b,&c);
 add(a,b,c);
 add(b,a,c);
 }
 }
 int main()
 {
    while(scanf("%d%d",&n,&m),n|m)
     {
     init();
     getmp();
     SPFA(1);
     }
 return 0;
 }