#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
//#define endl '\n'
#define F first
#define S second
int const M = 1e6 + 10 , N = 1e3 + 10 , mod = 1e9 + 7;
ll T , n , m , k , cost , x , y , s , t , u , v , type , ans = 1e18 , dis[6][M] , cnt[M] , on[M] , U[M] , V[M];
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1};
priority_queue<pair<ll , ll> , vector<pair<ll , ll>> , greater<pair<ll , ll>>>q;
vector<pair<ll , ll>>adj[M];
vector<ll>graph[M] , top;
bool vis[M];
inline void Dijkstra(int start) {
q.push({0 , start});
while(q.size()) {
int node = q.top().S;
int cost = q.top().F;
q.pop();
if(dis[type][node] || (node == start && cost)) continue;
dis[type][node] = cost;
for(auto next : adj[node]) q.push({cost + next.S , next.F});
}
}
inline void Bfs() {
queue<ll>Q;
Q.push(s);
while(Q.size()) {
int node = Q.front();
Q.pop();
top.push_back(node);
for(auto next : graph[node]) {
--cnt[next];
if(cnt[next] == 0) Q.push(next);
}
}
}
main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1 ; i <= m ; ++i) {
cin >> x >> y >> cost;
adj[x].push_back({y , cost});
adj[y].push_back({x , cost});
}
type = 1; Dijkstra(u);
type = 2; Dijkstra(v);
type = 3; Dijkstra(s);
type = 4; Dijkstra(t);
for(int node = 1 ; node <= n ; ++node) if(dis[3][node] + dis[4][node] == dis[3][t]) on[node] = 1;
for(int node = 1 ; node <= n ; ++node)
if(on[node])
for(auto next : adj[node])
if(on[next.F] && dis[3][node] + next.S == dis[3][next.F]) {
++cnt[next.F];
graph[node].push_back(next.F);
}
Bfs();
for(int i = 1 ; i <= n ; ++i) U[i] = V[i] = 1e18;
ans = dis[1][v];
for(auto node : top) {
ans = min(ans , dis[1][node] + V[node]);
ans = min(ans , dis[2][node] + U[node]);
U[node] = min(U[node] , dis[1][node]);
V[node] = min(V[node] , dis[2][node]);
for(auto next : graph[node]) U[next] = min(U[next] , U[node]) , V[next] = min(V[next] , V[node]);
}
cout << ans << endl;
return 0;
}
Compilation message
commuter_pass.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
65204 KB |
Output is correct |
2 |
Correct |
426 ms |
67084 KB |
Output is correct |
3 |
Correct |
438 ms |
73140 KB |
Output is correct |
4 |
Correct |
452 ms |
68672 KB |
Output is correct |
5 |
Correct |
425 ms |
71348 KB |
Output is correct |
6 |
Correct |
462 ms |
69048 KB |
Output is correct |
7 |
Correct |
446 ms |
72076 KB |
Output is correct |
8 |
Correct |
424 ms |
71728 KB |
Output is correct |
9 |
Correct |
462 ms |
69552 KB |
Output is correct |
10 |
Correct |
452 ms |
69548 KB |
Output is correct |
11 |
Correct |
156 ms |
62280 KB |
Output is correct |
12 |
Correct |
459 ms |
69636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
453 ms |
67024 KB |
Output is correct |
2 |
Correct |
437 ms |
70400 KB |
Output is correct |
3 |
Correct |
424 ms |
70224 KB |
Output is correct |
4 |
Correct |
417 ms |
70140 KB |
Output is correct |
5 |
Correct |
419 ms |
70620 KB |
Output is correct |
6 |
Correct |
429 ms |
72256 KB |
Output is correct |
7 |
Correct |
420 ms |
72368 KB |
Output is correct |
8 |
Correct |
418 ms |
70304 KB |
Output is correct |
9 |
Correct |
405 ms |
70884 KB |
Output is correct |
10 |
Correct |
435 ms |
70168 KB |
Output is correct |
11 |
Correct |
145 ms |
63240 KB |
Output is correct |
12 |
Correct |
431 ms |
72436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
49268 KB |
Output is correct |
2 |
Correct |
22 ms |
47428 KB |
Output is correct |
3 |
Correct |
23 ms |
47332 KB |
Output is correct |
4 |
Correct |
82 ms |
51864 KB |
Output is correct |
5 |
Correct |
51 ms |
50116 KB |
Output is correct |
6 |
Correct |
23 ms |
47444 KB |
Output is correct |
7 |
Correct |
26 ms |
47568 KB |
Output is correct |
8 |
Correct |
27 ms |
47696 KB |
Output is correct |
9 |
Correct |
25 ms |
47448 KB |
Output is correct |
10 |
Correct |
52 ms |
50160 KB |
Output is correct |
11 |
Correct |
25 ms |
47408 KB |
Output is correct |
12 |
Correct |
25 ms |
47332 KB |
Output is correct |
13 |
Correct |
23 ms |
47380 KB |
Output is correct |
14 |
Correct |
23 ms |
47496 KB |
Output is correct |
15 |
Correct |
23 ms |
47480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
65204 KB |
Output is correct |
2 |
Correct |
426 ms |
67084 KB |
Output is correct |
3 |
Correct |
438 ms |
73140 KB |
Output is correct |
4 |
Correct |
452 ms |
68672 KB |
Output is correct |
5 |
Correct |
425 ms |
71348 KB |
Output is correct |
6 |
Correct |
462 ms |
69048 KB |
Output is correct |
7 |
Correct |
446 ms |
72076 KB |
Output is correct |
8 |
Correct |
424 ms |
71728 KB |
Output is correct |
9 |
Correct |
462 ms |
69552 KB |
Output is correct |
10 |
Correct |
452 ms |
69548 KB |
Output is correct |
11 |
Correct |
156 ms |
62280 KB |
Output is correct |
12 |
Correct |
459 ms |
69636 KB |
Output is correct |
13 |
Correct |
453 ms |
67024 KB |
Output is correct |
14 |
Correct |
437 ms |
70400 KB |
Output is correct |
15 |
Correct |
424 ms |
70224 KB |
Output is correct |
16 |
Correct |
417 ms |
70140 KB |
Output is correct |
17 |
Correct |
419 ms |
70620 KB |
Output is correct |
18 |
Correct |
429 ms |
72256 KB |
Output is correct |
19 |
Correct |
420 ms |
72368 KB |
Output is correct |
20 |
Correct |
418 ms |
70304 KB |
Output is correct |
21 |
Correct |
405 ms |
70884 KB |
Output is correct |
22 |
Correct |
435 ms |
70168 KB |
Output is correct |
23 |
Correct |
145 ms |
63240 KB |
Output is correct |
24 |
Correct |
431 ms |
72436 KB |
Output is correct |
25 |
Correct |
55 ms |
49268 KB |
Output is correct |
26 |
Correct |
22 ms |
47428 KB |
Output is correct |
27 |
Correct |
23 ms |
47332 KB |
Output is correct |
28 |
Correct |
82 ms |
51864 KB |
Output is correct |
29 |
Correct |
51 ms |
50116 KB |
Output is correct |
30 |
Correct |
23 ms |
47444 KB |
Output is correct |
31 |
Correct |
26 ms |
47568 KB |
Output is correct |
32 |
Correct |
27 ms |
47696 KB |
Output is correct |
33 |
Correct |
25 ms |
47448 KB |
Output is correct |
34 |
Correct |
52 ms |
50160 KB |
Output is correct |
35 |
Correct |
25 ms |
47408 KB |
Output is correct |
36 |
Correct |
25 ms |
47332 KB |
Output is correct |
37 |
Correct |
23 ms |
47380 KB |
Output is correct |
38 |
Correct |
23 ms |
47496 KB |
Output is correct |
39 |
Correct |
23 ms |
47480 KB |
Output is correct |
40 |
Correct |
439 ms |
68752 KB |
Output is correct |
41 |
Correct |
441 ms |
69400 KB |
Output is correct |
42 |
Correct |
457 ms |
69384 KB |
Output is correct |
43 |
Correct |
166 ms |
64680 KB |
Output is correct |
44 |
Correct |
155 ms |
64708 KB |
Output is correct |
45 |
Correct |
452 ms |
73348 KB |
Output is correct |
46 |
Correct |
481 ms |
73028 KB |
Output is correct |
47 |
Correct |
440 ms |
69032 KB |
Output is correct |
48 |
Correct |
166 ms |
64124 KB |
Output is correct |
49 |
Correct |
433 ms |
67692 KB |
Output is correct |
50 |
Correct |
432 ms |
72232 KB |
Output is correct |
51 |
Correct |
446 ms |
73108 KB |
Output is correct |