poj3268 Silver Cow Party

思路：
最短路。
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <cstring>
 7 using namespace std;
 8 
 9 const int INF = 0x3f3f3f3f;
10 int d[1005], back[1005], times[1005];
11 bool in[1005];
12 struct edge
13 {
14     int t, w;
15     edge(int b, int c)
16     {
17         t = b; w = c;
18     }
19 };
20 vector<edge> G[1005];
21 int n, m, x, a, b, l;
22 
23 bool spfa(int s)
24 {
25     for (int i = 1; i <= n; i++)
26     {
27         d[i] = INF;
28         in[i] = false;
29         times[i] = 0;
30     }
31     queue<int> q;
32     q.push(s);
33     in[s] = true;
34     d[s] = 0;
35     while (!q.empty())
36     {
37         int tmp = q.front();
38         q.pop();
39         in[tmp] = false;
40         for (int i = 0; i < G[tmp].size(); i++)
41         {
42             if (d[tmp] + G[tmp][i].w < d[G[tmp][i].t])
43             {
44                 d[G[tmp][i].t] = d[tmp] + G[tmp][i].w;
45                 times[G[tmp][i].t]++;
46                 if (times[G[tmp][i].t] == n)
47                 {
48                     return false;
49                 }
50                 if (!in[G[tmp][i].t])
51                 {
52                     in[G[tmp][i].t] = true;
53                     q.push(G[tmp][i].t);
54                 }
55             }
56         }
57     }
58     return true;
59 }
60 
61 int main()
62 {
63     cin >> n >> m >> x;
64     for (int i = 0; i < m; i++)
65     {
66         scanf("%d %d %d", &a, &b, &l);
67         edge e(b, l);
68         G[a].push_back(e);
69     }
70     int maxn = 0;
71     spfa(x);
72     memcpy(back, d, (n + 1) * sizeof(int));
73     for (int i = 1; i <= n; i++)
74     {
75         spfa(i);
76         maxn = max(maxn, d[x] + back[i]);
77     }
78     cout << maxn << endl;
79     return 0;
80 }