#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
using ll = long long;
using li = pair<ll, int>;
const int N = (int)1e5 + 5, M = (int)2e5 + 5;
const ll infll = (ll)1e18 + 123;
int n, m, S, T, U, V;
ll ans;
vector< pair<int, int> > gr[N];
vector<int> Gr[N];
vector<ll> dS, dU, dV, dpU, dpV;
vector<bool> vis;
void dijkstra (int src, vector<ll> &d) {
d.assign(n + 5, infll); d[src] = 0;
priority_queue<li, vector<li>, greater<li> > pq; pq.push( { d[src], src } );
while (!pq.empty() ) {
li tmp = pq.top(); pq.pop();
int u = tmp.se;
if (d[u] < tmp.fi) continue ;
for (auto _ : gr[u]) {
int v = _.fi, w = _.se;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.push( { d[v], v } );
}
}
}
}
ll calc_dpU (int u) {
if (dpU[u] != -1) return dpU[u];
dpU[u] = dU[u];
for (int v : Gr[u]) dpU[u] = min(dpU[u], calc_dpU(v) );
return dpU[u];
}
ll calc_dpV (int u) {
if (dpV[u] != -1) return dpV[u];
dpV[u] = dV[u];
for (int v : Gr[u]) dpV[u] = min(dpV[u], calc_dpV(v) );
return dpV[u];
}
void trace (int u) {
if (vis[u] || u == S) return ;
vis[u] = 1;
for (auto _ : gr[u]) {
int v = _.fi, w = _.se;
if (dS[v] + w == dS[u]) Gr[v].pb(u), trace(v);
}
}
void dfs (int u) {
if (vis[u]) return ;
vis[u] = 1;
ans = min(ans, dU[u] + dpV[u]);
ans = min(ans, dV[u] + dpU[u]);
for (int v : Gr[u]) dfs(v);
}
int main () {
scanf("%d %d %d %d %d %d", &n, &m, &S, &T, &U, &V);
while (m --) {
int a, b, c; scanf("%d %d %d", &a, &b, &c);
gr[a].pb( { b, c } );
gr[b].pb( { a, c } );
}
dijkstra(S, dS);
dijkstra(U, dU);
dijkstra(V, dV);
vis.assign(n + 5, 0);
trace(T);
dpU.assign(n + 5, -1);
calc_dpU(S);
dpV.assign(n + 5, -1);
calc_dpV(S);
ans = dU[V];
vis.assign(n + 5, 0);
dfs(S);
printf("%lld", ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:69: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:71:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b, c; scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
20788 KB |
Output is correct |
2 |
Correct |
339 ms |
19192 KB |
Output is correct |
3 |
Correct |
457 ms |
23732 KB |
Output is correct |
4 |
Correct |
314 ms |
20692 KB |
Output is correct |
5 |
Correct |
318 ms |
19836 KB |
Output is correct |
6 |
Correct |
333 ms |
20788 KB |
Output is correct |
7 |
Correct |
374 ms |
20400 KB |
Output is correct |
8 |
Correct |
357 ms |
20096 KB |
Output is correct |
9 |
Correct |
324 ms |
19820 KB |
Output is correct |
10 |
Correct |
283 ms |
19800 KB |
Output is correct |
11 |
Correct |
135 ms |
17400 KB |
Output is correct |
12 |
Correct |
338 ms |
19872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
363 ms |
20436 KB |
Output is correct |
2 |
Correct |
367 ms |
20804 KB |
Output is correct |
3 |
Correct |
361 ms |
20192 KB |
Output is correct |
4 |
Correct |
362 ms |
20684 KB |
Output is correct |
5 |
Correct |
381 ms |
21112 KB |
Output is correct |
6 |
Correct |
341 ms |
23160 KB |
Output is correct |
7 |
Correct |
441 ms |
23524 KB |
Output is correct |
8 |
Correct |
355 ms |
20812 KB |
Output is correct |
9 |
Correct |
378 ms |
21020 KB |
Output is correct |
10 |
Correct |
345 ms |
20312 KB |
Output is correct |
11 |
Correct |
172 ms |
19064 KB |
Output is correct |
12 |
Correct |
368 ms |
23476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
6008 KB |
Output is correct |
2 |
Correct |
8 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
4984 KB |
Output is correct |
4 |
Correct |
25 ms |
7032 KB |
Output is correct |
5 |
Correct |
16 ms |
6008 KB |
Output is correct |
6 |
Correct |
7 ms |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
8 ms |
5240 KB |
Output is correct |
9 |
Correct |
7 ms |
5112 KB |
Output is correct |
10 |
Correct |
15 ms |
6008 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5032 KB |
Output is correct |
13 |
Correct |
6 ms |
4988 KB |
Output is correct |
14 |
Correct |
7 ms |
5116 KB |
Output is correct |
15 |
Correct |
7 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
20788 KB |
Output is correct |
2 |
Correct |
339 ms |
19192 KB |
Output is correct |
3 |
Correct |
457 ms |
23732 KB |
Output is correct |
4 |
Correct |
314 ms |
20692 KB |
Output is correct |
5 |
Correct |
318 ms |
19836 KB |
Output is correct |
6 |
Correct |
333 ms |
20788 KB |
Output is correct |
7 |
Correct |
374 ms |
20400 KB |
Output is correct |
8 |
Correct |
357 ms |
20096 KB |
Output is correct |
9 |
Correct |
324 ms |
19820 KB |
Output is correct |
10 |
Correct |
283 ms |
19800 KB |
Output is correct |
11 |
Correct |
135 ms |
17400 KB |
Output is correct |
12 |
Correct |
338 ms |
19872 KB |
Output is correct |
13 |
Correct |
363 ms |
20436 KB |
Output is correct |
14 |
Correct |
367 ms |
20804 KB |
Output is correct |
15 |
Correct |
361 ms |
20192 KB |
Output is correct |
16 |
Correct |
362 ms |
20684 KB |
Output is correct |
17 |
Correct |
381 ms |
21112 KB |
Output is correct |
18 |
Correct |
341 ms |
23160 KB |
Output is correct |
19 |
Correct |
441 ms |
23524 KB |
Output is correct |
20 |
Correct |
355 ms |
20812 KB |
Output is correct |
21 |
Correct |
378 ms |
21020 KB |
Output is correct |
22 |
Correct |
345 ms |
20312 KB |
Output is correct |
23 |
Correct |
172 ms |
19064 KB |
Output is correct |
24 |
Correct |
368 ms |
23476 KB |
Output is correct |
25 |
Correct |
17 ms |
6008 KB |
Output is correct |
26 |
Correct |
8 ms |
5112 KB |
Output is correct |
27 |
Correct |
7 ms |
4984 KB |
Output is correct |
28 |
Correct |
25 ms |
7032 KB |
Output is correct |
29 |
Correct |
16 ms |
6008 KB |
Output is correct |
30 |
Correct |
7 ms |
5112 KB |
Output is correct |
31 |
Correct |
7 ms |
5112 KB |
Output is correct |
32 |
Correct |
8 ms |
5240 KB |
Output is correct |
33 |
Correct |
7 ms |
5112 KB |
Output is correct |
34 |
Correct |
15 ms |
6008 KB |
Output is correct |
35 |
Correct |
6 ms |
4984 KB |
Output is correct |
36 |
Correct |
6 ms |
5032 KB |
Output is correct |
37 |
Correct |
6 ms |
4988 KB |
Output is correct |
38 |
Correct |
7 ms |
5116 KB |
Output is correct |
39 |
Correct |
7 ms |
5112 KB |
Output is correct |
40 |
Correct |
312 ms |
21056 KB |
Output is correct |
41 |
Correct |
307 ms |
19908 KB |
Output is correct |
42 |
Correct |
384 ms |
19852 KB |
Output is correct |
43 |
Correct |
169 ms |
19704 KB |
Output is correct |
44 |
Correct |
154 ms |
19704 KB |
Output is correct |
45 |
Correct |
356 ms |
21436 KB |
Output is correct |
46 |
Correct |
384 ms |
21344 KB |
Output is correct |
47 |
Correct |
305 ms |
20520 KB |
Output is correct |
48 |
Correct |
156 ms |
17656 KB |
Output is correct |
49 |
Correct |
274 ms |
20724 KB |
Output is correct |
50 |
Correct |
387 ms |
20816 KB |
Output is correct |
51 |
Correct |
393 ms |
21444 KB |
Output is correct |