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
| #include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define eps 1e-8
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1e3 + 5;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
struct edge {
int u, v, w, ne;
} ed[2][M];
int vis[2][N], head[2][N], dis[2][N];
int n, m, cnt[2];
void add(int op, int u, int v, int w) {
ed[op][cnt[op]] = {u, v, w, head[op][u]};
head[op][u] = cnt[op]++;
}
void init() {
memset(vis, 0, sizeof vis);
memset(head, -1, sizeof head);
memset(dis, INF, sizeof dis);
cnt[0] = cnt[1] = 0;
}
void dijk(int op, int s) {
priority_queue<P, vector<P> , greater<P> > q;
dis[op][s] = 0;
q.push(P(0, s));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[op][u]) continue;
vis[op][u] = 1;
for (int i = head[op][u]; ~i; i = ed[op][i].ne) {
int v = ed[op][i].v, w = ed[op][i].w;
if (dis[op][v] > dis[op][u] + w)
dis[op][v] = dis[op][u] + w, q.push(P(dis[op][v], v));
}
}
}
int main(){
n = read(), m = read();
int x = read();
init();
while(m--){
int u = read(), v = read(), w = read();
add(0, u, v, w);
add(1, v, u, w);
}
dijk(0, x);
dijk(1, x);
int ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, dis[0][i] + dis[1][i]);
cout << ans << "\n";
return 0;
}
|