POJ-2387 Til the Cows Come Home(SPFA)

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <queue>
 6 #include <stack>
 7 #include <vector>
 8 #include <iostream>
 9 #include "algorithm"
10 using namespace std;
11 const int MAX=2005;
12 const int INF=0x3f3f3f3f;
13 int n,m,tot;
14 int head[MAX],adj[MAX*2],next[MAX*2],wei[MAX*2];
15 int map[MAX][MAX];
16 int dist[MAX];
17 bool vis[MAX];
18 void addedge(int u,int v,int w){
19     tot++;
20     adj[tot]=v;
21     next[tot]=head[u];
22     wei[tot]=w;
23     head[u]=tot;
24 }
25 void spfa(){
26     int i,j,x;
27     queue <int> q;
28     while (!q.empty()) q.pop();
29     q.push(1);
30     memset(vis,false,sizeof(vis));vis[1]=true;
31     while (!q.empty()){
32         x=q.front();q.pop();vis[x]=false;
33         for (i=head[x];i!=-1;i=next[i])
34             if (dist[adj[i]]>dist[x]+wei[i]){
35                 dist[adj[i]]=dist[x]+wei[i];
36                 if (!vis[adj[i]]){
37                     q.push(adj[i]);
38                     vis[adj[i]]=true;
39                 }
40             }
41     }
42 }
43 int main(){
44     freopen ("home.in","r",stdin);
45     freopen ("home.out","w",stdout);
46     int i,j;int u,v,w;
47     while(scanf("%d%d",&m,&n)!=EOF){
48         tot=0;
49         memset(head,-1,sizeof(head));
50         memset(dist,INF,sizeof(dist));dist[1]=0;
51         memset(map,INF,sizeof(map));
52         for (i=1;i<=m;i++){
53             scanf("%d%d%d",&u,&v,&w);
54             map[u][v]=map[v][u]=min(map[u][v],w);
55         }
56         for (i=1;i<=n;i++)
57             for (j=i+1;j<=n;j++)
58                 if (map[i][j]!=INF){
59                     addedge(i,j,map[i][j]);
60                     addedge(j,i,map[i][j]);
61                 }
62         spfa();
63         printf("%d\n",dist[n]);
64     }
65     return 0;
66 }