大意:不再赘述,牛牛们一定可以到达目的地,当然也可以走回去。
思路:建立正、反向图,使用spfa,Dijkstra,枚举最大值均可。
CODE:
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1010; const int MAXM = 100010; struct Edge { int v, next, w; }edge[MAXM]; int n, m, src; int cnt; int first[MAXN], d[MAXN], ans[MAXN]; int su[MAXM], sv[MAXM], sw[MAXM]; int MaxTime; inline void read_graph(int u, int v, int w) { edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = first[u], first[u] = cnt++; } inline void init() { cnt = 0; MaxTime = 0; memset(first, -1, sizeof(first)); } void spfa(int src) { queue<int> q; bool inq[MAXN] = {0}; for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF; q.push(src); while(!q.empty()) { int x = q.front(); q.pop(); inq[x] = 0; for(int e = first[x]; e != -1; e = edge[e].next) { int v = edge[e].v, w = edge[e].w; if(d[v] > d[x] + w) { d[v] = d[x] + w; if(!inq[v]) { inq[v] = 1; q.push(v); } } } } } void solve() { init(); for(int i = 0; i < m; i++) { scanf("%d%d%d", &su[i], &sv[i], &sw[i]); read_graph(su[i], sv[i], sw[i]); } spfa(src); for(int i = 1; i <= n; i++) ans[i] += d[i]; init(); for(int i = 0; i < m; i++) read_graph(sv[i], su[i], sw[i]); spfa(src); for(int i = 1; i <= n; i++) { ans[i] += d[i]; MaxTime = max(MaxTime, ans[i]); } printf("%d\n", MaxTime); } int main() { while(~scanf("%d%d%d", &n, &m, &src)) { solve(); } return 0; }