#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e6+50, mod = 1e9+7, K = 31;
int n,m;
int S,T,U,V;
int x,y,w;
vector<pair<int,int>>gr[N];
ll D[5][N];
int A[5],ind[5];
ll dp[5][N];
inline void dijkstra(int x){
priority_queue<pair<ll,int>>q;
vector<int>fix(n+5,0);
int a = ind[x];
for(int i = 1; i <= n; i++){
D[a][i] = 1e18;
}
D[a][x] = 0;
q.push({0,x});
while(q.size()){
auto p = q.top();
q.pop();
int x = p.ss;
ll dist = -p.ff;
if(fix[x]) continue;
fix[x] = 1;
//cout << x << " " ;
for(auto pp : gr[x]){
int to = pp.ff;
ll w = pp.ss;
ll new_dist = dist + w;
if(D[a][to] > new_dist){
D[a][to] = new_dist;
q.push({-new_dist,to});
}
}
}
}
ll dist_st;
inline bool on_pass(int x){
return dist_st == (D[ind[S]][x] + D[ind[T]][x]);
}
inline void bfs(int X){
vector<pair<ll,int>>v;
for(int i = 1; i <= n; i++){
if(on_pass(i)){
v.pb({D[ind[X]][i],i});
}
}
int a = ind[X];
sort(v.begin(),v.end());
for(int i = 0; i < v.size(); i++){
int x = v[i].ss;
//cout << x << endl;
dp[a][x] = min(dp[a][x],D[ind[U]][x]);
for(auto pp : gr[x]){
int to = pp.ff;
dp[a][x] = min(dp[a][x],dp[a][to]);
}
}
}
inline void test_case(){
cin >> n >> m;
for(int i = 1; i <= 4; i++){
cin >> A[i];
ind[A[i]] = i;
}
S = A[1]; T = A[2]; U = A[3]; V = A[4];
for(int i = 1; i <= m; i++){
cin >> x >> y >> w;
gr[x].pb({y,w});
gr[y].pb({x,w});
}
for(int i = 1; i <= 4; i++) dijkstra(A[i]);
dist_st = D[ind[S]][T];
for(int i = 1; i <= n; i++) dp[ind[S]][i] = dp[ind[T]][i] = 1e18;
bfs(S);
bfs(T);
ll answer = D[ind[U]][V];
for(int i = 1; i <= n; i++){
//cout << i << " " << dp[ind[S]][i] << " " << dp[ind[T]][i] << endl;
answer = min(answer, min(dp[ind[S]][i], dp[ind[T]][i]) + D[ind[V]][i]);
}
cout << answer << endl;
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i <= T; i++){
test_case();
}
}
Compilation message
commuter_pass.cpp: In function 'void bfs(int)':
commuter_pass.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:112:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
112 | main(){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
317 ms |
35984 KB |
Output is correct |
2 |
Correct |
315 ms |
35112 KB |
Output is correct |
3 |
Correct |
393 ms |
37020 KB |
Output is correct |
4 |
Correct |
327 ms |
35960 KB |
Output is correct |
5 |
Correct |
330 ms |
35964 KB |
Output is correct |
6 |
Correct |
327 ms |
36072 KB |
Output is correct |
7 |
Correct |
334 ms |
36204 KB |
Output is correct |
8 |
Correct |
330 ms |
35988 KB |
Output is correct |
9 |
Correct |
333 ms |
34696 KB |
Output is correct |
10 |
Correct |
263 ms |
34656 KB |
Output is correct |
11 |
Correct |
155 ms |
32668 KB |
Output is correct |
12 |
Correct |
329 ms |
34788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
358 ms |
35692 KB |
Output is correct |
2 |
Correct |
340 ms |
35860 KB |
Output is correct |
3 |
Correct |
329 ms |
35668 KB |
Output is correct |
4 |
Correct |
357 ms |
35744 KB |
Output is correct |
5 |
Correct |
340 ms |
36492 KB |
Output is correct |
6 |
Correct |
326 ms |
36708 KB |
Output is correct |
7 |
Correct |
378 ms |
38172 KB |
Output is correct |
8 |
Correct |
361 ms |
35964 KB |
Output is correct |
9 |
Correct |
353 ms |
36572 KB |
Output is correct |
10 |
Correct |
388 ms |
35896 KB |
Output is correct |
11 |
Correct |
138 ms |
33816 KB |
Output is correct |
12 |
Correct |
335 ms |
37220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
24524 KB |
Output is correct |
2 |
Correct |
14 ms |
23884 KB |
Output is correct |
3 |
Correct |
14 ms |
23884 KB |
Output is correct |
4 |
Correct |
30 ms |
25908 KB |
Output is correct |
5 |
Correct |
23 ms |
24976 KB |
Output is correct |
6 |
Correct |
16 ms |
23876 KB |
Output is correct |
7 |
Correct |
16 ms |
24012 KB |
Output is correct |
8 |
Correct |
16 ms |
24012 KB |
Output is correct |
9 |
Correct |
15 ms |
23972 KB |
Output is correct |
10 |
Correct |
23 ms |
24844 KB |
Output is correct |
11 |
Correct |
15 ms |
23812 KB |
Output is correct |
12 |
Correct |
15 ms |
23884 KB |
Output is correct |
13 |
Correct |
15 ms |
23884 KB |
Output is correct |
14 |
Correct |
16 ms |
23864 KB |
Output is correct |
15 |
Correct |
15 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
317 ms |
35984 KB |
Output is correct |
2 |
Correct |
315 ms |
35112 KB |
Output is correct |
3 |
Correct |
393 ms |
37020 KB |
Output is correct |
4 |
Correct |
327 ms |
35960 KB |
Output is correct |
5 |
Correct |
330 ms |
35964 KB |
Output is correct |
6 |
Correct |
327 ms |
36072 KB |
Output is correct |
7 |
Correct |
334 ms |
36204 KB |
Output is correct |
8 |
Correct |
330 ms |
35988 KB |
Output is correct |
9 |
Correct |
333 ms |
34696 KB |
Output is correct |
10 |
Correct |
263 ms |
34656 KB |
Output is correct |
11 |
Correct |
155 ms |
32668 KB |
Output is correct |
12 |
Correct |
329 ms |
34788 KB |
Output is correct |
13 |
Correct |
358 ms |
35692 KB |
Output is correct |
14 |
Correct |
340 ms |
35860 KB |
Output is correct |
15 |
Correct |
329 ms |
35668 KB |
Output is correct |
16 |
Correct |
357 ms |
35744 KB |
Output is correct |
17 |
Correct |
340 ms |
36492 KB |
Output is correct |
18 |
Correct |
326 ms |
36708 KB |
Output is correct |
19 |
Correct |
378 ms |
38172 KB |
Output is correct |
20 |
Correct |
361 ms |
35964 KB |
Output is correct |
21 |
Correct |
353 ms |
36572 KB |
Output is correct |
22 |
Correct |
388 ms |
35896 KB |
Output is correct |
23 |
Correct |
138 ms |
33816 KB |
Output is correct |
24 |
Correct |
335 ms |
37220 KB |
Output is correct |
25 |
Correct |
21 ms |
24524 KB |
Output is correct |
26 |
Correct |
14 ms |
23884 KB |
Output is correct |
27 |
Correct |
14 ms |
23884 KB |
Output is correct |
28 |
Correct |
30 ms |
25908 KB |
Output is correct |
29 |
Correct |
23 ms |
24976 KB |
Output is correct |
30 |
Correct |
16 ms |
23876 KB |
Output is correct |
31 |
Correct |
16 ms |
24012 KB |
Output is correct |
32 |
Correct |
16 ms |
24012 KB |
Output is correct |
33 |
Correct |
15 ms |
23972 KB |
Output is correct |
34 |
Correct |
23 ms |
24844 KB |
Output is correct |
35 |
Correct |
15 ms |
23812 KB |
Output is correct |
36 |
Correct |
15 ms |
23884 KB |
Output is correct |
37 |
Correct |
15 ms |
23884 KB |
Output is correct |
38 |
Correct |
16 ms |
23864 KB |
Output is correct |
39 |
Correct |
15 ms |
23884 KB |
Output is correct |
40 |
Correct |
307 ms |
41048 KB |
Output is correct |
41 |
Correct |
316 ms |
39756 KB |
Output is correct |
42 |
Correct |
317 ms |
39712 KB |
Output is correct |
43 |
Correct |
156 ms |
37408 KB |
Output is correct |
44 |
Correct |
158 ms |
37496 KB |
Output is correct |
45 |
Correct |
320 ms |
41948 KB |
Output is correct |
46 |
Correct |
329 ms |
41608 KB |
Output is correct |
47 |
Correct |
322 ms |
40452 KB |
Output is correct |
48 |
Correct |
152 ms |
36828 KB |
Output is correct |
49 |
Correct |
275 ms |
40532 KB |
Output is correct |
50 |
Correct |
314 ms |
41760 KB |
Output is correct |
51 |
Correct |
309 ms |
41800 KB |
Output is correct |