pku2387 Til the Cows Come Home

http://poj.org/problem?id=2387

图论，最短路

单源最短路，Dijkstra O（N^2）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 1234
 4 
 5 const int inf = 1<<25;
 6 int n;
 7 int path[N], vis[N];
 8 int cost[N][N], lowcost[N];
 9 
10 void dijkstra(int beg)
11 {
12     int i, j, min1;
13     memset(vis, 0, sizeof(vis));
14     vis[beg] = 1;
15     for(i=0; i<n; i++)
16     {
17         lowcost[i] = cost[beg][i];
18         path[i] = beg;
19     }
20     lowcost[beg] = 0;
21     path[beg] = -1;
22     int pre = beg;
23     for(i=1; i<n; i++)
24     {
25         min1 = inf;
26         for(j=0; j<n; j++)
27         {
28             if(vis[j]==0 && lowcost[pre]+cost[pre][j]<lowcost[j])
29             {
30                 lowcost[j] = lowcost[pre] + cost[pre][j];
31                 path[j] = pre;
32             }
33         }
34         for(j=0; j<n; j++)
35         {
36             if(vis[j] == 0 && lowcost[j] < min1)
37             {
38                 min1 = lowcost[j];
39                 pre = j;
40             }
41         }
42         vis[pre] = 1;
43     }
44 }
45 
46 
47 int main()
48 {
49     int t, i, j, x, y, len;
50     scanf("%d%d", &t, &n);
51     for(i=0; i<n; i++)
52     {
53         for(j=0; j<n; j++)
54         {
55             cost[i][j] = inf;
56         }
57     }
58     for(i=1; i<=t; i++)
59     {
60         scanf("%d%d%d", &x, &y, &len);
61         if(len < cost[x-1][y-1])
62         {
63             cost[x-1][y-1] = cost[y-1][x-1] = len;
64         }
65     }
66     dijkstra(0);
67     printf("%d\n", lowcost[n-1]);
68     return 0;
69 }

单源最短路，SPFA，O（V*E）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #define N 1234
 5 
 6 using namespace std;
 7 
 8 int n, m, src;
 9 vector<pair<int, int> > g[N];
10 int dist[N];
11 bool inQue[N];
12 queue<int> que;
13 
14 void spfa()
15 {
16     memset(dist, 63, sizeof(dist));
17     dist[src] = 0;
18     while(!que.empty())
19     {
20         que.pop();
21     }
22     que.push(src);
23     inQue[src] = true;
24     while(!que.empty())
25     {
26         int u = que.front();
27         que.pop();
28         for(int i=0; i<g[u].size(); i++)
29         {
30             if(dist[u] + g[u][i].second < dist[g[u][i].first])
31             {
32                 dist[g[u][i].first] = dist[u] + g[u][i].second;
33                 if(!inQue[g[u][i].first])
34                 {
35                     inQue[g[u][i].first] = true;
36                     que.push(g[u][i].first);
37                 }
38             }
39         }
40         inQue[u] = false;
41     }
42 }
43 
44 int main()
45 {
46     int t, i, j, x, y, len;
47     pair<int, int> pair1;
48     scanf("%d%d", &t, &n);
49     for(i=1; i<=t; i++)
50     {
51         scanf("%d%d%d", &x, &y, &len);
52         g[x].push_back(make_pair(y, len));
53         g[y].push_back(make_pair(x, len));
54     }
55     src = 1;
56     spfa();
57     printf("%d\n", dist[n]);
58     return 0;
59 }

floyd求图中任意两点间距离 O(N^3)，对于本题会TLE

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 1234
 4 
 5 int n, g[N][N];
 6 const int inf = 1<<29;
 7 
 8 int min(int x, int y)
 9 {
10     return x<y? x: y; 
11 }
12 
13 void floyd()
14 {
15     int i, j, k;
16     for(k=1; k<=n; k++)
17     {
18         for(i=1; i<=n; i++)
19         {
20             for(j=1; j<=n; j++)
21             {
22                 g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
23             }
24         }
25     }
26 }
27 
28 int main()
29 {
30     int t, i, j, x, y, len;
31     scanf("%d%d", &t, &n);
32     for(i=1; i<=n; i++)
33     {
34         for(j=1; j<=n; j++)
35         {
36             g[i][j] = inf;
37         }
38     }
39     for(i=1; i<=t; i++)
40     {
41         scanf("%d%d%d", &x, &y, &len);
42         if(len < g[x][y])
43         {
44             g[x][y] = g[y][x] = len;
45         }
46     }
47     floyd();
48     printf("%d\n", g[n][1]);
49     return 0;
50 }