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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
inline int __read()
{
int x(0), t(1);
char o (getchar());
while (o < '0' || o > '9') {
if (o == '-') t = -1;
o = getchar();
}
for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
return x * t;
}
int T, P, R, S, cur, dis[maxn];
int hed[maxn], edg[maxn], nxt[maxn], cst[maxn];
inline void AddEdge(int u, int v, int w)
{
nxt[++cur] = hed[u];
hed[u] = cur;
edg[cur] = v;
cst[cur] = w;
}
bool vis[maxn];
inline void SPFA()
{
deque <int> Q;
Q.push_front(S);
dis[S] = 0;
while (!Q.empty()) {
int now = Q.front();
Q.pop_front();
vis[now] = 0;
for (int i = hed[now]; i; i = nxt[i]) {
if (dis[edg[i]] <= cst[i] + dis[now]) continue;
dis[edg[i]] = cst[i] + dis[now];
if (vis[edg[i]]) continue;
vis[edg[i]] = 1;
if (Q.empty() || dis[edg[i]] <= dis[Q.front()]) Q.push_front(edg[i]);
else Q.push_back(edg[i]);
}
}
}
int main()
{
T = __read(), R = __read(), P = __read(), S = __read();
while (R--) {
int a = __read(), b = __read(), c = __read();
AddEdge(a, b, c), AddEdge(b, a, c);
}
while (P--) {
int a = __read(), b = __read(), c = __read();
AddEdge(a, b, c);
}
memset (dis, 0x3f, sizeof dis);
SPFA();
for (int i = 1; i <= T; ++i) {
if (dis[i] == inf) puts("NO PATH");
else printf ("%d\n", dis[i]);
}
system("pause");
}
|