PS： 对原图和反图求最短路，然后求最长的即可。省赛热身练习。
#include#include #include #include #include #include using namespace std; const int maxn = 1010; const int INF = 0x3ffffff; //Accepted 468K 63MS struct edges { int from, to, w; }; int n, m, s; int d1[maxn]; int d2[maxn]; queue que; bool inque[maxn]; void spfa(vector G[], int d[]) { while(!que.empty()) que.pop(); memset(inque, false, sizeof(inque)); for(int i = 1; i <= n; i++) d[i] = INF; d[s] = 0; inque[s] = true; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = 0; i < (int)G[u].size(); i++) { edges v = G[u][i]; if(d[u]!=INF && d[u]+v.w < d[v.to]) { d[v.to] = d[u] + v.w; if(!inque[v.to]) { inque[v.to] = true; que.push(v.to); } } } inque[u] = false; } } int work() { int ans = -INF; for(int i = 1; i <= n; i++) { if(d1[i]+d2[i]>ans) { ans = d1[i] + d2[i]; } } return ans; } vector G[maxn]; vector RG[maxn]; int main() { edges t; int from, to, w; while(scanf("%d%d%d", &n, &m, &s)!=EOF) { for(int i = 1; i <= m; i++) { scanf("%d%d%d", &from, &to, &w); t.from = from; t.to = to; t.w = w; G[from].push_back(t); t.from = to; t.to = from; RG[t.from].push_back(t); } spfa(G, d1); spfa(RG, d2); int res = work(); printf("%d\n", res); } return 0; }