#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll INF=1e18+7;
vector<pair<int,ll>>V[LIM];
ll wart[LIM][2], odl[LIM][2], mi[LIM][2], n, m;
void dijkstra1(int x, int k) {
rep(i, n) wart[i][k]=INF;
priority_queue<pair<ll,int>>q;
q.push({0, x});
while(!q.empty()) {
ll o=-q.top().st, p=q.top().nd; q.pop();
if(wart[p][k]<=o) continue;
wart[p][k]=o;
for(auto i : V[p]) if(o+i.nd<wart[i.st][k]) {
q.push({-o-i.nd, i.st});
}
}
}
void dijkstra2(int x, int k) {
rep(i, n) odl[i][k]=mi[i][k]=INF;
priority_queue<pair<pair<ll,ll>,int>>q;
q.push({{0, -wart[x][0]}, x});
while(!q.empty()) {
ll a=-q.top().st.st, b=-q.top().st.nd, p=q.top().nd; q.pop();
if(odl[p][k]<a) continue;
if(odl[p][k]==a && mi[p][k]<=b) continue;
odl[p][k]=a;
mi[p][k]=b;
for(auto i : V[p]) {
if(a+i.nd<odl[i.st][k] || a+i.nd==odl[i.st][k] && min(b, wart[i.st][0])<mi[i.st][0]) {
q.push({{-a-i.nd, -min(b, wart[i.st][0])}, i.st});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
--s; --t; --u; --v;
rep(i, m) {
int a, b, c;
cin >> a >> b >> c; --a; --b;
V[a].pb({b, c});
V[b].pb({a, c});
}
dijkstra1(u, 0);
dijkstra1(v, 1);
dijkstra2(s, 0);
dijkstra2(t, 1);
ll ans=wart[v][0];
rep(i, n) if(odl[i][0]+odl[i][1]==odl[t][0]) {
ans=min(ans, wart[i][1]+min(mi[i][0], mi[i][1]));
}
cout << ans << '\n';
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:38:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
38 | if(a+i.nd<odl[i.st][k] || a+i.nd==odl[i.st][k] && min(b, wart[i.st][0])<mi[i.st][0]) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
27272 KB |
Output is correct |
2 |
Correct |
353 ms |
26376 KB |
Output is correct |
3 |
Correct |
368 ms |
26724 KB |
Output is correct |
4 |
Correct |
367 ms |
26928 KB |
Output is correct |
5 |
Correct |
347 ms |
25800 KB |
Output is correct |
6 |
Correct |
367 ms |
27292 KB |
Output is correct |
7 |
Correct |
363 ms |
26272 KB |
Output is correct |
8 |
Correct |
381 ms |
26236 KB |
Output is correct |
9 |
Correct |
359 ms |
27180 KB |
Output is correct |
10 |
Correct |
400 ms |
27220 KB |
Output is correct |
11 |
Correct |
154 ms |
14512 KB |
Output is correct |
12 |
Correct |
387 ms |
27212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
369 ms |
26636 KB |
Output is correct |
2 |
Correct |
350 ms |
26180 KB |
Output is correct |
3 |
Correct |
384 ms |
26024 KB |
Output is correct |
4 |
Correct |
334 ms |
26024 KB |
Output is correct |
5 |
Correct |
366 ms |
25936 KB |
Output is correct |
6 |
Correct |
340 ms |
26532 KB |
Output is correct |
7 |
Correct |
356 ms |
25908 KB |
Output is correct |
8 |
Correct |
340 ms |
25968 KB |
Output is correct |
9 |
Correct |
353 ms |
25964 KB |
Output is correct |
10 |
Correct |
357 ms |
26048 KB |
Output is correct |
11 |
Correct |
115 ms |
14560 KB |
Output is correct |
12 |
Correct |
386 ms |
26596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5132 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2672 KB |
Output is correct |
4 |
Correct |
41 ms |
7560 KB |
Output is correct |
5 |
Correct |
22 ms |
5584 KB |
Output is correct |
6 |
Correct |
2 ms |
2764 KB |
Output is correct |
7 |
Correct |
3 ms |
2892 KB |
Output is correct |
8 |
Correct |
4 ms |
2940 KB |
Output is correct |
9 |
Correct |
3 ms |
2804 KB |
Output is correct |
10 |
Correct |
20 ms |
5120 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2676 KB |
Output is correct |
14 |
Correct |
3 ms |
2768 KB |
Output is correct |
15 |
Correct |
2 ms |
2764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
27272 KB |
Output is correct |
2 |
Correct |
353 ms |
26376 KB |
Output is correct |
3 |
Correct |
368 ms |
26724 KB |
Output is correct |
4 |
Correct |
367 ms |
26928 KB |
Output is correct |
5 |
Correct |
347 ms |
25800 KB |
Output is correct |
6 |
Correct |
367 ms |
27292 KB |
Output is correct |
7 |
Correct |
363 ms |
26272 KB |
Output is correct |
8 |
Correct |
381 ms |
26236 KB |
Output is correct |
9 |
Correct |
359 ms |
27180 KB |
Output is correct |
10 |
Correct |
400 ms |
27220 KB |
Output is correct |
11 |
Correct |
154 ms |
14512 KB |
Output is correct |
12 |
Correct |
387 ms |
27212 KB |
Output is correct |
13 |
Correct |
369 ms |
26636 KB |
Output is correct |
14 |
Correct |
350 ms |
26180 KB |
Output is correct |
15 |
Correct |
384 ms |
26024 KB |
Output is correct |
16 |
Correct |
334 ms |
26024 KB |
Output is correct |
17 |
Correct |
366 ms |
25936 KB |
Output is correct |
18 |
Correct |
340 ms |
26532 KB |
Output is correct |
19 |
Correct |
356 ms |
25908 KB |
Output is correct |
20 |
Correct |
340 ms |
25968 KB |
Output is correct |
21 |
Correct |
353 ms |
25964 KB |
Output is correct |
22 |
Correct |
357 ms |
26048 KB |
Output is correct |
23 |
Correct |
115 ms |
14560 KB |
Output is correct |
24 |
Correct |
386 ms |
26596 KB |
Output is correct |
25 |
Correct |
24 ms |
5132 KB |
Output is correct |
26 |
Correct |
2 ms |
2636 KB |
Output is correct |
27 |
Correct |
2 ms |
2672 KB |
Output is correct |
28 |
Correct |
41 ms |
7560 KB |
Output is correct |
29 |
Correct |
22 ms |
5584 KB |
Output is correct |
30 |
Correct |
2 ms |
2764 KB |
Output is correct |
31 |
Correct |
3 ms |
2892 KB |
Output is correct |
32 |
Correct |
4 ms |
2940 KB |
Output is correct |
33 |
Correct |
3 ms |
2804 KB |
Output is correct |
34 |
Correct |
20 ms |
5120 KB |
Output is correct |
35 |
Correct |
2 ms |
2636 KB |
Output is correct |
36 |
Correct |
2 ms |
2636 KB |
Output is correct |
37 |
Correct |
2 ms |
2676 KB |
Output is correct |
38 |
Correct |
3 ms |
2768 KB |
Output is correct |
39 |
Correct |
2 ms |
2764 KB |
Output is correct |
40 |
Correct |
375 ms |
26968 KB |
Output is correct |
41 |
Correct |
422 ms |
27168 KB |
Output is correct |
42 |
Correct |
371 ms |
27320 KB |
Output is correct |
43 |
Correct |
99 ms |
14660 KB |
Output is correct |
44 |
Correct |
118 ms |
14736 KB |
Output is correct |
45 |
Correct |
346 ms |
24044 KB |
Output is correct |
46 |
Correct |
370 ms |
23584 KB |
Output is correct |
47 |
Correct |
374 ms |
26760 KB |
Output is correct |
48 |
Correct |
122 ms |
14120 KB |
Output is correct |
49 |
Correct |
351 ms |
26412 KB |
Output is correct |
50 |
Correct |
339 ms |
23848 KB |
Output is correct |
51 |
Correct |
337 ms |
23884 KB |
Output is correct |