#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
const int len = 1e5+5;
const ll inf = 1e16;
int n, m, s1, t1, s2, t2, best[len];
ll dis[5][len];
vector<ii> adj[len];
priority_queue<pair<ll, ii>, vector<pair<ll, ii> >, greater<pair<ll, ii> > > pq;
void dfs(int u){
//printf("best %d\n", u);
best[u] = 1;
for (int j = 0; j < adj[u].size(); j++){
ii v = adj[u][j];
if (!best[v.fi] && dis[4][v.fi]+v.se == dis[4][u])
dfs(v.fi);
}
}
void path(int s, int hey){
if (!hey){
for (int j = 1; j <= n; j++)
dis[4][j] = inf;
}
else{
for (int i = 0; i < 4; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = inf;
}
if (!hey){
pq.push(mp(0, mp(4, s)));
}
else{
if (best[s])
pq.push(mp(0, mp(1, s))), pq.push(mp(0, mp(2, s)));
else
pq.push(mp(0, mp(0, s)));
}
while (!pq.empty()){
pair<ll, ii> top = pq.top();
pq.pop();
int t = top.se.fi, u = top.se.se;
ll d = top.fi;
if (dis[t][u] != inf)
continue;
dis[t][u] = d;
//printf("(%d, %d) -> %lld\n", t, u, d);
for (int j = 0; j < adj[u].size(); j++){
ii v = adj[u][j];
if (t == 0){
if (!best[v.fi])
pq.push(mp(d+v.se, mp(0, v.fi)));
else
pq.push(mp(d+v.se, mp(1, v.fi))), pq.push(mp(d+v.se, mp(2, v.fi)));
}
else if (t == 1){
if (best[v.fi] && dis[4][u]-dis[4][v.fi] == v.se)
pq.push(mp(d, mp(1, v.fi)));
else
pq.push(mp(d+v.se, mp(3, v.fi)));
}
else if (t == 2){
if (best[v.fi] && dis[4][u]-dis[4][v.fi] == -v.se)
pq.push(mp(d, mp(2, v.fi)));
else
pq.push(mp(d+v.se, mp(3, v.fi)));
}
else if (t == 3){
pq.push(mp(d+v.se, mp(3, v.fi)));
}
else{
pq.push(mp(d+v.se, mp(4, v.fi)));
}
}
}
}
int main(){
scanf("%d %d %d %d %d %d", &n, &m, &s1, &t1, &s2, &t2);
for (int i = 0; i < m; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}
path(s1, 0);
dfs(t1);
path(s2, 1);
ll ans = min(min(dis[0][t2], dis[1][t2]), min(dis[2][t2], dis[3][t2]));
printf("%lld\n", ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[u].size(); j++){
~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void path(int, int)':
commuter_pass.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adj[u].size(); j++){
~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93: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, &s1, &t1, &s2, &t2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:96: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 |
458 ms |
19572 KB |
Output is correct |
2 |
Correct |
597 ms |
24084 KB |
Output is correct |
3 |
Correct |
567 ms |
34924 KB |
Output is correct |
4 |
Correct |
446 ms |
34924 KB |
Output is correct |
5 |
Correct |
609 ms |
36024 KB |
Output is correct |
6 |
Correct |
466 ms |
38128 KB |
Output is correct |
7 |
Correct |
647 ms |
47720 KB |
Output is correct |
8 |
Correct |
654 ms |
47720 KB |
Output is correct |
9 |
Correct |
470 ms |
49488 KB |
Output is correct |
10 |
Correct |
454 ms |
53956 KB |
Output is correct |
11 |
Correct |
202 ms |
53956 KB |
Output is correct |
12 |
Correct |
476 ms |
60480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
594 ms |
65788 KB |
Output is correct |
2 |
Correct |
572 ms |
70388 KB |
Output is correct |
3 |
Correct |
705 ms |
77816 KB |
Output is correct |
4 |
Correct |
507 ms |
77816 KB |
Output is correct |
5 |
Correct |
533 ms |
80944 KB |
Output is correct |
6 |
Correct |
766 ms |
89408 KB |
Output is correct |
7 |
Correct |
801 ms |
93076 KB |
Output is correct |
8 |
Correct |
532 ms |
93076 KB |
Output is correct |
9 |
Correct |
513 ms |
95104 KB |
Output is correct |
10 |
Correct |
518 ms |
98236 KB |
Output is correct |
11 |
Correct |
249 ms |
98236 KB |
Output is correct |
12 |
Correct |
803 ms |
109348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
109348 KB |
Output is correct |
2 |
Correct |
6 ms |
109348 KB |
Output is correct |
3 |
Correct |
6 ms |
109348 KB |
Output is correct |
4 |
Correct |
59 ms |
109348 KB |
Output is correct |
5 |
Correct |
43 ms |
109348 KB |
Output is correct |
6 |
Correct |
6 ms |
109348 KB |
Output is correct |
7 |
Incorrect |
8 ms |
109348 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
458 ms |
19572 KB |
Output is correct |
2 |
Correct |
597 ms |
24084 KB |
Output is correct |
3 |
Correct |
567 ms |
34924 KB |
Output is correct |
4 |
Correct |
446 ms |
34924 KB |
Output is correct |
5 |
Correct |
609 ms |
36024 KB |
Output is correct |
6 |
Correct |
466 ms |
38128 KB |
Output is correct |
7 |
Correct |
647 ms |
47720 KB |
Output is correct |
8 |
Correct |
654 ms |
47720 KB |
Output is correct |
9 |
Correct |
470 ms |
49488 KB |
Output is correct |
10 |
Correct |
454 ms |
53956 KB |
Output is correct |
11 |
Correct |
202 ms |
53956 KB |
Output is correct |
12 |
Correct |
476 ms |
60480 KB |
Output is correct |
13 |
Correct |
594 ms |
65788 KB |
Output is correct |
14 |
Correct |
572 ms |
70388 KB |
Output is correct |
15 |
Correct |
705 ms |
77816 KB |
Output is correct |
16 |
Correct |
507 ms |
77816 KB |
Output is correct |
17 |
Correct |
533 ms |
80944 KB |
Output is correct |
18 |
Correct |
766 ms |
89408 KB |
Output is correct |
19 |
Correct |
801 ms |
93076 KB |
Output is correct |
20 |
Correct |
532 ms |
93076 KB |
Output is correct |
21 |
Correct |
513 ms |
95104 KB |
Output is correct |
22 |
Correct |
518 ms |
98236 KB |
Output is correct |
23 |
Correct |
249 ms |
98236 KB |
Output is correct |
24 |
Correct |
803 ms |
109348 KB |
Output is correct |
25 |
Correct |
40 ms |
109348 KB |
Output is correct |
26 |
Correct |
6 ms |
109348 KB |
Output is correct |
27 |
Correct |
6 ms |
109348 KB |
Output is correct |
28 |
Correct |
59 ms |
109348 KB |
Output is correct |
29 |
Correct |
43 ms |
109348 KB |
Output is correct |
30 |
Correct |
6 ms |
109348 KB |
Output is correct |
31 |
Incorrect |
8 ms |
109348 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |