#include <bits/stdc++.h>
#define long long long
#define pii pair<long, long>
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
vector<pii> g[N];
void sssp(int src, long d[]) {
fill_n(d, N, 1e18);
priority_queue<pii, vector<pii>, greater<pii> > Q;
Q.emplace(d[src] = 0, src);
while(!Q.empty()) {
pii now = Q.top(); Q.pop();
if(d[now.y] != now.x) continue;
long u, w; tie(w, u) = now;
for(pii v : g[u]) if(w + v.y < d[v.x])
Q.emplace(d[v.x] = w + v.y, v.x);
}
}
int n, m, s, t, u, v;
long ds[N], dt[N], du[N], dv[N];
long solve(int a, int b, long da[], long db[]) {
long dp[N], len = da[b];
bool vis[N]; memset(vis, 0, sizeof vis);
priority_queue<pii, vector<pii>, greater<pii> > Q;
for(int i = 1; i <= n; i++) dp[i] = du[i];
Q.emplace(0, a), vis[a] = true;
while(!Q.empty()) {
pii now = Q.top(); Q.pop();
if(now.x != da[now.y]) continue;
long u, w; tie(w, u) = now;
for(pii v : g[u]) if(w + v.y + db[v.x] == len) {
dp[v.x] = min(dp[v.x], dp[u]);
if(!vis[v.x]) vis[v.x] = true, Q.emplace(w + v.y, v.x);
}
}
long ret = 1e18;
for(int i = 1; i <= n; i++) if(da[i] + db[i] == len)
ret = min(ret, dp[i] + dv[i]);
return ret;
}
int main() {
scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
for(int i = 1, a, b, c; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
sssp(s, ds), sssp(t, dt);
sssp(u, du), sssp(v, dv);
printf("%lld\n", min({du[v], solve(s, t, ds, dt), solve(t, s, dt, ds)}));
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
449 ms |
19420 KB |
Output is correct |
2 |
Correct |
428 ms |
18196 KB |
Output is correct |
3 |
Correct |
433 ms |
18768 KB |
Output is correct |
4 |
Correct |
395 ms |
19316 KB |
Output is correct |
5 |
Correct |
423 ms |
18060 KB |
Output is correct |
6 |
Correct |
416 ms |
19336 KB |
Output is correct |
7 |
Correct |
460 ms |
18024 KB |
Output is correct |
8 |
Correct |
443 ms |
18180 KB |
Output is correct |
9 |
Correct |
427 ms |
18108 KB |
Output is correct |
10 |
Correct |
352 ms |
17916 KB |
Output is correct |
11 |
Correct |
168 ms |
11900 KB |
Output is correct |
12 |
Correct |
431 ms |
18060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
18164 KB |
Output is correct |
2 |
Correct |
443 ms |
18812 KB |
Output is correct |
3 |
Correct |
448 ms |
18856 KB |
Output is correct |
4 |
Correct |
449 ms |
18824 KB |
Output is correct |
5 |
Correct |
449 ms |
18872 KB |
Output is correct |
6 |
Correct |
433 ms |
18676 KB |
Output is correct |
7 |
Correct |
477 ms |
18796 KB |
Output is correct |
8 |
Correct |
449 ms |
18892 KB |
Output is correct |
9 |
Correct |
440 ms |
18828 KB |
Output is correct |
10 |
Correct |
442 ms |
18812 KB |
Output is correct |
11 |
Correct |
172 ms |
12668 KB |
Output is correct |
12 |
Correct |
439 ms |
18596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
7160 KB |
Output is correct |
2 |
Correct |
7 ms |
5880 KB |
Output is correct |
3 |
Correct |
9 ms |
5880 KB |
Output is correct |
4 |
Correct |
28 ms |
9284 KB |
Output is correct |
5 |
Correct |
17 ms |
7672 KB |
Output is correct |
6 |
Correct |
8 ms |
6008 KB |
Output is correct |
7 |
Correct |
8 ms |
6136 KB |
Output is correct |
8 |
Correct |
9 ms |
6136 KB |
Output is correct |
9 |
Correct |
8 ms |
6008 KB |
Output is correct |
10 |
Correct |
17 ms |
7544 KB |
Output is correct |
11 |
Correct |
7 ms |
6008 KB |
Output is correct |
12 |
Correct |
7 ms |
5880 KB |
Output is correct |
13 |
Correct |
7 ms |
6012 KB |
Output is correct |
14 |
Correct |
7 ms |
6008 KB |
Output is correct |
15 |
Correct |
7 ms |
6008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
449 ms |
19420 KB |
Output is correct |
2 |
Correct |
428 ms |
18196 KB |
Output is correct |
3 |
Correct |
433 ms |
18768 KB |
Output is correct |
4 |
Correct |
395 ms |
19316 KB |
Output is correct |
5 |
Correct |
423 ms |
18060 KB |
Output is correct |
6 |
Correct |
416 ms |
19336 KB |
Output is correct |
7 |
Correct |
460 ms |
18024 KB |
Output is correct |
8 |
Correct |
443 ms |
18180 KB |
Output is correct |
9 |
Correct |
427 ms |
18108 KB |
Output is correct |
10 |
Correct |
352 ms |
17916 KB |
Output is correct |
11 |
Correct |
168 ms |
11900 KB |
Output is correct |
12 |
Correct |
431 ms |
18060 KB |
Output is correct |
13 |
Correct |
452 ms |
18164 KB |
Output is correct |
14 |
Correct |
443 ms |
18812 KB |
Output is correct |
15 |
Correct |
448 ms |
18856 KB |
Output is correct |
16 |
Correct |
449 ms |
18824 KB |
Output is correct |
17 |
Correct |
449 ms |
18872 KB |
Output is correct |
18 |
Correct |
433 ms |
18676 KB |
Output is correct |
19 |
Correct |
477 ms |
18796 KB |
Output is correct |
20 |
Correct |
449 ms |
18892 KB |
Output is correct |
21 |
Correct |
440 ms |
18828 KB |
Output is correct |
22 |
Correct |
442 ms |
18812 KB |
Output is correct |
23 |
Correct |
172 ms |
12668 KB |
Output is correct |
24 |
Correct |
439 ms |
18596 KB |
Output is correct |
25 |
Correct |
17 ms |
7160 KB |
Output is correct |
26 |
Correct |
7 ms |
5880 KB |
Output is correct |
27 |
Correct |
9 ms |
5880 KB |
Output is correct |
28 |
Correct |
28 ms |
9284 KB |
Output is correct |
29 |
Correct |
17 ms |
7672 KB |
Output is correct |
30 |
Correct |
8 ms |
6008 KB |
Output is correct |
31 |
Correct |
8 ms |
6136 KB |
Output is correct |
32 |
Correct |
9 ms |
6136 KB |
Output is correct |
33 |
Correct |
8 ms |
6008 KB |
Output is correct |
34 |
Correct |
17 ms |
7544 KB |
Output is correct |
35 |
Correct |
7 ms |
6008 KB |
Output is correct |
36 |
Correct |
7 ms |
5880 KB |
Output is correct |
37 |
Correct |
7 ms |
6012 KB |
Output is correct |
38 |
Correct |
7 ms |
6008 KB |
Output is correct |
39 |
Correct |
7 ms |
6008 KB |
Output is correct |
40 |
Correct |
440 ms |
23128 KB |
Output is correct |
41 |
Correct |
409 ms |
22316 KB |
Output is correct |
42 |
Correct |
409 ms |
22372 KB |
Output is correct |
43 |
Correct |
203 ms |
14272 KB |
Output is correct |
44 |
Correct |
215 ms |
14072 KB |
Output is correct |
45 |
Correct |
503 ms |
22136 KB |
Output is correct |
46 |
Correct |
461 ms |
22016 KB |
Output is correct |
47 |
Correct |
402 ms |
23044 KB |
Output is correct |
48 |
Correct |
330 ms |
13432 KB |
Output is correct |
49 |
Correct |
340 ms |
22768 KB |
Output is correct |
50 |
Correct |
450 ms |
21512 KB |
Output is correct |
51 |
Correct |
441 ms |
21948 KB |
Output is correct |