POJ2387 Til the Cows Come Home(SPFA + dijkstra + BallemFord 模板)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <vector>
 5 #include <cstring>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 const int INF = 10000000;
10 const int MAX = 1000 + 10;
11 int t,n;
12 struct point
13 {
14     int e,w;
15 };
16 vector<point> g[MAX];
17 int dist[MAX];
18 void spfa(int v)
19 {
20     for(int i = 0; i <= n; i++)
21     {
22         dist[i] = INF;
23     }
24     dist[v] = 0;
25     queue<int> que;
26     que.push(v);
27     while(que.size())
28     {
29         int x = que.front();
30         que.pop();
31         int len = g[x].size();
32         for(int i = 0; i < len; i++)
33         {
34             int y = g[x][i].e;
35             if(dist[y] > dist[x] + g[x][i].w)
36             {
37                 dist[y] = dist[x] + g[x][i].w;
38                 que.push(y);
39             }
40         }
41     }
42 }
43 int main()
44 {
45     while(scanf("%d%d", &t, &n) != EOF)
46     {
47         for(int i = 0; i < MAX; i++)
48             g[i].clear();
49 
50         while(t--)
51         {
52             int s,e,w;
53             point temp;
54             scanf("%d%d%d", &s,&e,&w);
55             temp.w = w;
56             temp.e = e;
57             g[s].push_back(temp);
58             temp.e = s;
59             g[e].push_back(temp);
60         }
61 
62         spfa(n);
63         printf("%d\n",dist[1]);
64     }
65 
66     return 0;
67 }

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string.h>
 5 using namespace std;
 6 const int INF = 10000000;
 7 const int MAX = 1000 + 10;
 8 int g[MAX][MAX],dist[MAX],vis[MAX];
 9 int t,n;
10 void Dijkstra()
11 {
12     for(int i = 1; i <= n; i++)
13         dist[i] = INF;
14     memset(vis,0,sizeof(vis));
15     dist[n] = 0;
16     vis[n] = 0;
17     int pos = n;
18     for(int i = 1; i < n; i++)
19     {
20         int minn = INF;
21         for(int j = 1; j <= n; j++)
22         {
23             if(vis[j] == 0 && dist[j] < minn)
24             {
25                 minn = dist[j];
26                 pos = j;
27             }
28         }
29         vis[pos] = 1;
30         for(int j = 1; j <= n; j ++)
31         {
32             if(vis[j] == 0 && dist[j] > dist[pos] + g[pos][j])
33                 dist[j] = dist[pos] + g[pos][j];
34         }
35     }
36 }
37 int main()
38 {
39     while(scanf("%d%d",&t,&n) != EOF)
40     {
41         int s,e,w;
42         for(int i = 1; i <= n; i++)
43         {
44             for(int j = 1; j <= n; j++)
45             {
46                 g[i][j] = INF;
47             }
48         }
49         for(int i = 0; i < t; i++)
50         {
51             scanf("%d%d%d",&s,&e,&w);
52             if(g[s][e] > w)
53                 g[s][e] = g[e][s] = w;
54         }
55         Dijkstra();
56         printf("%d\n",dist[1]);
57     }
58 
59 }

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <iostream>
 7 using namespace std;
 8 const int INF = 1000000000;
 9 const int MAX = 1000 + 10;
10 int n,t;
11 struct point
12 {
13     int s,t,w;
14 };
15 vector<point> g;
16 int dist[MAX];
17 void Ballem_ford(int v)
18 {
19     for(int i = 1; i <= n; i++)
20         dist[i] = INF;
21     dist[v] = 0;
22     for(int i = 1; i < n; i++)
23     {
24         int len = g.size();
25         int flag = 0;
26         for(int i = 0; i < len; i++)
27         {
28              int s = g[i].s;
29              int t = g[i].t;
30              int w = g[i].w;
31              if(dist[t] > dist[s] + w)
32              {
33                  dist[t] = dist[s] + w;
34                  flag = 1;
35              }
36         }
37         if(flag == 0)   //加个flag 优化一下瞬间由47ms变成16ms
38             break;
39     }
40 }
41 int main()
42 {
43     while(scanf("%d%d", &t, &n) != EOF)
44     {
45         g.clear();
46         int s,e,w;
47         point temp;
48         for(int i = 0; i < t; i++)
49         {
50             scanf("%d%d%d", &s,&e,&w);
51             temp.w = w;
52             temp.t = e;
53             temp.s = s;
54             g.push_back(temp);
55             temp.t = s;
56             temp.s = e;
57             g.push_back(temp);
58         }
59         Ballem_ford(n);
60         printf("%d\n",dist[1]);
61     }
62 }