凑数用的。。。其实是刚写了个spfa的板子，感觉很好而已。。。
每个点spfa一边就过了。。。蒟蒻都觉得水。。。
1 /************************************************************** 2 Problem: 1631 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:196 ms 7 Memory:2380 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 1005; 16 struct edge{ 17 int next, to, v; 18 }e[100005]; 19 int n, m, S, X, Y, Z, tot; 20 int q[100005], dis[N], first[N], dis1[N], ANS; 21 bool v[N]; 22 23 inline int read(){ 24 int x = 0, sgn = 1; 25 char ch = getchar(); 26 while (ch < '0' || ch > '9'){ 27 if (ch == '-') sgn = -1; 28 ch = getchar(); 29 } 30 while (ch >= '0' && ch <= '9'){ 31 x = x * 10 + ch - '0'; 32 ch = getchar(); 33 } 34 return sgn * x; 35 } 36 37 inline void add_edge(int x, int y, int z){ 38 e[++tot].next = first[x], first[x] = tot; 39 e[tot].to = y, e[tot].v = z; 40 } 41 42 void spfa(int S){ 43 memset(dis, 127, sizeof(dis)); 44 q[0] = S, dis[S] = 0, v[S] = 1; 45 int p, x, y; 46 for (int l = 0, r = 0; l <= r; ++l){ 47 p = q[l]; 48 for (x = first[p]; x; x = e[x].next){ 49 y = e[x].to; 50 if (dis[p] + e[x].v < dis[y]){ 51 dis[y] = dis[p] + e[x].v; 52 if (!v[y]) 53 v[y] = 1, q[++r] = y; 54 } 55 } 56 v[p] = 0; 57 } 58 } 59 60 int main(){ 61 n = read(), m = read(), S = read(); 62 for (int i = 1; i <= m; ++i){ 63 X = read(), Y = read(), Z = read(); 64 add_edge(X, Y, Z); 65 } 66 for (int i = 1; i <= n; ++i){ 67 spfa(i); 68 dis1[i] = dis[S]; 69 } 70 spfa(S); 71 for (int i = 1; i <= n; ++i) 72 ANS = max(ANS, dis[i] + dis1[i]); 73 printf("%d ", ANS); 74 return 0; 75 }
（p.s. 感觉做法已经很快了啊。。。那些20ms的人心态呢。。。都是怎么做的。。。）