Dijkstra!
一群牛（ N 隻牛）要參加派對，他們分別來自 N 個不同的農場（每個農場標記成 ），要去 X 號農場參加派對。農場間共有 M 條單向道路，每條路 需要耗時 的時間。
每隻牛都必須參加派對，因為他們很懶，所以一定要走最短的距離，從自己的農場走到派對農場，然後以最短路徑，再從派對農場走回自己的農場。
假設全部的牛都以上述最優方式走動，花費最多時間的牛要花費多少時間走路？
第一行 3 個正整數 ，代表有 個農場、 條路、派對辦在 號農場。 接下來有 行，第 行有 三個數字，代表一條路從 到 ，需要耗時 秒。
輸出一個整數，代表花費最多時間的牛要花費多少時間走路。
需要做兩次 Dijkstra ，一次從 出發，算出從 到所有點的的最短距離， 另一次將所有邊反轉，從 出發，可以算出從每個點到 的最短距離。 之後講上述兩者相加，得到對於所有節點 ，從 -> -> 的最短距離，就可以求出最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define W first
#define T second
using namespace std;
class Solution {
typedef pair<int,int> EDGE; // weight, to
private:
vector< EDGE > *V;
vector< EDGE > *R;
int *dist, *rdist;
int N, M, X;
int infi;
void init() {
V = new vector< EDGE >[N+1];
R = new vector< EDGE >[N+1];
dist = new int[N+1];
rdist = new int[N+1];
}
inline void link(int u, int v, int w) {
V[u].push_back(make_pair(w,v));
R[v].push_back(make_pair(w,u));
}
void des() {
delete[] R; delete[] V;
delete[] dist; delete[] rdist;
}
void read_data() {
scanf("%d%d%d", &N, &M, &X);
--X;
init();
int u, v, w;
for(int i=0; i!=M; ++i) {
scanf("%d%d%d",&u,&v,&w);
link(u-1,v-1,w);//0-base
}
}
void dij( vector< EDGE >*& E, int *&d, int src ) {
priority_queue< EDGE, vector< EDGE >, greater< EDGE > > que;
fill(d,d+N,infi);
d[src]=0;
que.push(make_pair(0,src));
while(!que.empty()) {
EDGE pii=que.top(); que.pop();
if(pii.W>d[pii.T]) continue;
for( vector< EDGE >::iterator v=E[pii.T].begin(); v!=E[pii.T].end(); ++v) {
if(d[v->T]>pii.W+v->W) {
d[v->T]=pii.W+v->W;
que.push(make_pair(d[v->T], v->T));
}
}
}
}
void print_dist() {
for(int i=0; i!=N; ++i) printf("%d ", dist[i]);
puts("");
for(int i=0; i!=N; ++i) printf("%d ", rdist[i]);
puts("");
}
int find_max() {
int res=-1e9;
for(int i=0; i!=N; ++i) res=max(res,dist[i]+rdist[i]);
return res;
}
public:
int solv() {
read_data();
dij(V, dist, X);
dij(R, rdist, X);
int res=find_max();
//print_dist();
des();
return res;
}
Solution(){
infi=1e9+7;
}
};
int main(void) {
Solution sol;
printf("%d\n",sol.solv());
return 0;
}