#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int N, M, S, T, U, V;
ll minD;
vlm Sd, Td, Ud, Vd;
vim Gr[100010]; vlm C[100010];
vim G1[100010], G2[100010];
vim chk, ts1, ts2, loc1, loc2; vlm Um, Vm;
priority_queue<pli, vector<pli>, greater<pli> > pq;
void TS1(int now) {
chk[now]=1;
for (int i:G1[now]) {
if (!chk[i]) TS1(i);
}
ts1.push_back(now);
}
void TS2(int now) {
chk[now]=1;
for (int i:G2[now]) {
if (!chk[i]) TS2(i);
}
ts2.push_back(now);
}
int main() {
int im1, im2, im3;
scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
for (int i=0; i<M; i++) {
scanf("%d %d %d", &im1, &im2, &im3);
Gr[im1].push_back(im2); C[im1].push_back((ll)im3);
Gr[im2].push_back(im1); C[im2].push_back((ll)im3);
}
Sd.resize(N+1); Td.resize(N+1); Ud.resize(N+1); Vd.resize(N+1); chk.resize(N+1);
fill(all(chk), 0); while(!pq.empty()) pq.pop();
pq.push({0, S});
while (!pq.empty()) {
pli pi=pq.top(); pq.pop();
if (chk[pi.se]) continue;
chk[pi.se]=1; Sd[pi.se]=pi.fi;
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
}
fill(all(chk), 0); while(!pq.empty()) pq.pop();
pq.push({0, T});
while (!pq.empty()) {
pli pi=pq.top(); pq.pop();
if (chk[pi.se]) continue;
chk[pi.se]=1; Td[pi.se]=pi.fi;
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
}
fill(all(chk), 0); while(!pq.empty()) pq.pop();
pq.push({0, U});
while (!pq.empty()) {
pli pi=pq.top(); pq.pop();
if (chk[pi.se]) continue;
chk[pi.se]=1; Ud[pi.se]=pi.fi;
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
}
fill(all(chk), 0); while(!pq.empty()) pq.pop();
pq.push({0, V});
while (!pq.empty()) {
pli pi=pq.top(); pq.pop();
if (chk[pi.se]) continue;
chk[pi.se]=1; Vd[pi.se]=pi.fi;
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
}
minD=Sd[T];
for (int i=1; i<=N; i++) for (int j=0; j<Gr[i].size(); j++) if (minD==Sd[i]+Td[Gr[i][j]]+C[i][j]) {
G1[i].push_back(Gr[i][j]);
G2[Gr[i][j]].push_back(i);
}
fill(all(chk), 0); TS1(S);
fill(all(chk), 0); TS2(T);
reverse(all(ts1)); reverse(all(ts2));
Um.resize(ts1.size()); Vm.resize(ts1.size()); loc1.resize(N+1); loc2.resize(N+1);
for (int i=0; i<ts1.size(); i++) loc1[ts1[i]]=loc2[ts2[i]]=i;
ll ans=Ud[V];
fill(all(Um), (1ll<<60)); fill(all(Vm), (1ll<<60));
for (int i=0; i<ts1.size(); i++) {
Um[i]=min(Um[i], Ud[ts1[i]]); Vm[i]=min(Vm[i], Vd[ts1[i]]);
ans=min(ans, min(Um[i]+Vd[ts1[i]], Vm[i]+Ud[ts1[i]]));
for (int j:G1[ts1[i]]) {
Um[loc1[j]]=min(Um[loc1[j]], Um[i]);
Vm[loc1[j]]=min(Vm[loc1[j]], Vm[i]);
}
}
fill(all(Um), (1ll<<60)); fill(all(Vm), (1ll<<60));
for (int i=0; i<ts2.size(); i++) {
Um[i]=min(Um[i], Ud[ts2[i]]); Vm[i]=min(Vm[i], Vd[ts2[i]]);
ans=min(ans, min(Um[i]+Vd[ts2[i]], Vm[i]+Ud[ts2[i]]));
for (int j:G2[ts2[i]]) {
Um[loc2[j]]=min(Um[loc2[j]], Um[i]);
Vm[loc2[j]]=min(Vm[loc2[j]], Vm[i]);
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<Gr[pi.se].size(); i++) if (!chk[Gr[pi.se][i]]) pq.push({pi.fi+C[pi.se][i], Gr[pi.se][i]});
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:87:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<=N; i++) for (int j=0; j<Gr[i].size(); j++) if (minD==Sd[i]+Td[Gr[i][j]]+C[i][j]) {
~^~~~~~~~~~~~~
commuter_pass.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ts1.size(); i++) loc1[ts1[i]]=loc2[ts2[i]]=i;
~^~~~~~~~~~~
commuter_pass.cpp:101:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ts1.size(); i++) {
~^~~~~~~~~~~
commuter_pass.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<ts2.size(); i++) {
~^~~~~~~~~~~
commuter_pass.cpp:41:7: 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:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &im1, &im2, &im3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
547 ms |
30064 KB |
Output is correct |
2 |
Correct |
606 ms |
31292 KB |
Output is correct |
3 |
Correct |
654 ms |
37608 KB |
Output is correct |
4 |
Correct |
545 ms |
29916 KB |
Output is correct |
5 |
Correct |
656 ms |
32980 KB |
Output is correct |
6 |
Correct |
588 ms |
30056 KB |
Output is correct |
7 |
Correct |
610 ms |
34076 KB |
Output is correct |
8 |
Correct |
616 ms |
33384 KB |
Output is correct |
9 |
Correct |
550 ms |
30188 KB |
Output is correct |
10 |
Correct |
540 ms |
30328 KB |
Output is correct |
11 |
Correct |
289 ms |
28024 KB |
Output is correct |
12 |
Correct |
593 ms |
30196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
609 ms |
32596 KB |
Output is correct |
2 |
Correct |
585 ms |
32620 KB |
Output is correct |
3 |
Correct |
577 ms |
31868 KB |
Output is correct |
4 |
Correct |
591 ms |
32476 KB |
Output is correct |
5 |
Correct |
592 ms |
33420 KB |
Output is correct |
6 |
Correct |
607 ms |
36976 KB |
Output is correct |
7 |
Correct |
708 ms |
37244 KB |
Output is correct |
8 |
Correct |
607 ms |
32744 KB |
Output is correct |
9 |
Correct |
594 ms |
33600 KB |
Output is correct |
10 |
Correct |
589 ms |
32028 KB |
Output is correct |
11 |
Correct |
320 ms |
30836 KB |
Output is correct |
12 |
Correct |
789 ms |
37432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
11512 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
13 ms |
9736 KB |
Output is correct |
4 |
Correct |
67 ms |
13300 KB |
Output is correct |
5 |
Correct |
40 ms |
11636 KB |
Output is correct |
6 |
Correct |
12 ms |
9848 KB |
Output is correct |
7 |
Correct |
13 ms |
9848 KB |
Output is correct |
8 |
Correct |
14 ms |
9976 KB |
Output is correct |
9 |
Correct |
13 ms |
9852 KB |
Output is correct |
10 |
Correct |
36 ms |
11740 KB |
Output is correct |
11 |
Correct |
11 ms |
9720 KB |
Output is correct |
12 |
Correct |
11 ms |
9720 KB |
Output is correct |
13 |
Correct |
11 ms |
9848 KB |
Output is correct |
14 |
Correct |
11 ms |
9848 KB |
Output is correct |
15 |
Correct |
12 ms |
9832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
547 ms |
30064 KB |
Output is correct |
2 |
Correct |
606 ms |
31292 KB |
Output is correct |
3 |
Correct |
654 ms |
37608 KB |
Output is correct |
4 |
Correct |
545 ms |
29916 KB |
Output is correct |
5 |
Correct |
656 ms |
32980 KB |
Output is correct |
6 |
Correct |
588 ms |
30056 KB |
Output is correct |
7 |
Correct |
610 ms |
34076 KB |
Output is correct |
8 |
Correct |
616 ms |
33384 KB |
Output is correct |
9 |
Correct |
550 ms |
30188 KB |
Output is correct |
10 |
Correct |
540 ms |
30328 KB |
Output is correct |
11 |
Correct |
289 ms |
28024 KB |
Output is correct |
12 |
Correct |
593 ms |
30196 KB |
Output is correct |
13 |
Correct |
609 ms |
32596 KB |
Output is correct |
14 |
Correct |
585 ms |
32620 KB |
Output is correct |
15 |
Correct |
577 ms |
31868 KB |
Output is correct |
16 |
Correct |
591 ms |
32476 KB |
Output is correct |
17 |
Correct |
592 ms |
33420 KB |
Output is correct |
18 |
Correct |
607 ms |
36976 KB |
Output is correct |
19 |
Correct |
708 ms |
37244 KB |
Output is correct |
20 |
Correct |
607 ms |
32744 KB |
Output is correct |
21 |
Correct |
594 ms |
33600 KB |
Output is correct |
22 |
Correct |
589 ms |
32028 KB |
Output is correct |
23 |
Correct |
320 ms |
30836 KB |
Output is correct |
24 |
Correct |
789 ms |
37432 KB |
Output is correct |
25 |
Correct |
37 ms |
11512 KB |
Output is correct |
26 |
Correct |
11 ms |
9720 KB |
Output is correct |
27 |
Correct |
13 ms |
9736 KB |
Output is correct |
28 |
Correct |
67 ms |
13300 KB |
Output is correct |
29 |
Correct |
40 ms |
11636 KB |
Output is correct |
30 |
Correct |
12 ms |
9848 KB |
Output is correct |
31 |
Correct |
13 ms |
9848 KB |
Output is correct |
32 |
Correct |
14 ms |
9976 KB |
Output is correct |
33 |
Correct |
13 ms |
9852 KB |
Output is correct |
34 |
Correct |
36 ms |
11740 KB |
Output is correct |
35 |
Correct |
11 ms |
9720 KB |
Output is correct |
36 |
Correct |
11 ms |
9720 KB |
Output is correct |
37 |
Correct |
11 ms |
9848 KB |
Output is correct |
38 |
Correct |
11 ms |
9848 KB |
Output is correct |
39 |
Correct |
12 ms |
9832 KB |
Output is correct |
40 |
Correct |
534 ms |
29952 KB |
Output is correct |
41 |
Correct |
559 ms |
30252 KB |
Output is correct |
42 |
Correct |
572 ms |
30204 KB |
Output is correct |
43 |
Correct |
339 ms |
33512 KB |
Output is correct |
44 |
Correct |
359 ms |
33552 KB |
Output is correct |
45 |
Correct |
742 ms |
36676 KB |
Output is correct |
46 |
Correct |
752 ms |
36432 KB |
Output is correct |
47 |
Correct |
564 ms |
29804 KB |
Output is correct |
48 |
Correct |
383 ms |
31472 KB |
Output is correct |
49 |
Correct |
532 ms |
29592 KB |
Output is correct |
50 |
Correct |
678 ms |
35156 KB |
Output is correct |
51 |
Correct |
737 ms |
36592 KB |
Output is correct |