#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int MAXN = 1e5, INF = 1e18;
vector<vector<pair<int, int>>> g(MAXN);
vector<int> distS(MAXN, INF), distT(MAXN, INF), distA(MAXN, INF), distB(MAXN, INF);
int n, m, s, t, a, b, x, y, z;
void dijkstra(int r, vector<int> &dist){
priority_queue<pair<int, int>> q;
dist[r] = 0;
q.emplace(0, r);
while(!q.empty()){
int u = q.top().second, d = -q.top().first; q.pop();
if(d != dist[u]) continue;
for(auto &e : g[u]){
int v = e.first, w = e.second;
if(dist[v] > d + w){
dist[v] = d + w;
q.emplace(-(d + w), v);
}
}
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> s >> t >> a >> b;
--s, --t, --a, --b;
while(m--){
cin >> x >> y >> z; --x, --y;
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
dijkstra(s, distS);
dijkstra(t, distT);
dijkstra(a, distA);
dijkstra(b, distB);
int shortest = distS[t];
vector<array<int, 2>> dp(n, {INF, INF});
vector<pair<int, int>> onPath;
for(int i=0; i<n; ++i){
if(distS[i] + distT[i] == shortest) onPath.emplace_back(distS[i], i);
}
int ans = distA[b];
sort(onPath.begin(), onPath.end());
for(auto &i : onPath){
int u = i.second;
dp[u][0] = min(dp[u][0], distA[u]);
dp[u][1] = min(dp[u][1], distB[u]);
ans = min(ans, dp[u][0] + distB[u]);
ans = min(ans, dp[u][1] + distA[u]);
for(auto &e : g[u]){
int v = e.first, w = e.second;
dp[v][0] = min(dp[v][0], dp[u][0]);
dp[v][1] = min(dp[v][1], dp[u][1]);
}
}
cout << ans;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:21: warning: unused variable 'w' [-Wunused-variable]
70 | int v = e.first, w = e.second;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
23112 KB |
Output is correct |
2 |
Correct |
334 ms |
22172 KB |
Output is correct |
3 |
Correct |
345 ms |
24628 KB |
Output is correct |
4 |
Correct |
321 ms |
22996 KB |
Output is correct |
5 |
Correct |
340 ms |
23024 KB |
Output is correct |
6 |
Correct |
337 ms |
23252 KB |
Output is correct |
7 |
Correct |
354 ms |
23316 KB |
Output is correct |
8 |
Correct |
332 ms |
22940 KB |
Output is correct |
9 |
Correct |
332 ms |
22392 KB |
Output is correct |
10 |
Correct |
287 ms |
22312 KB |
Output is correct |
11 |
Correct |
128 ms |
15676 KB |
Output is correct |
12 |
Correct |
354 ms |
22216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
351 ms |
22332 KB |
Output is correct |
2 |
Correct |
354 ms |
22384 KB |
Output is correct |
3 |
Correct |
348 ms |
22076 KB |
Output is correct |
4 |
Correct |
353 ms |
22144 KB |
Output is correct |
5 |
Correct |
361 ms |
22872 KB |
Output is correct |
6 |
Correct |
337 ms |
23356 KB |
Output is correct |
7 |
Correct |
374 ms |
24280 KB |
Output is correct |
8 |
Correct |
349 ms |
22356 KB |
Output is correct |
9 |
Correct |
372 ms |
22908 KB |
Output is correct |
10 |
Correct |
348 ms |
22116 KB |
Output is correct |
11 |
Correct |
147 ms |
15804 KB |
Output is correct |
12 |
Correct |
347 ms |
23648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
7500 KB |
Output is correct |
2 |
Correct |
4 ms |
5836 KB |
Output is correct |
3 |
Correct |
4 ms |
5820 KB |
Output is correct |
4 |
Correct |
18 ms |
9280 KB |
Output is correct |
5 |
Correct |
12 ms |
7500 KB |
Output is correct |
6 |
Correct |
4 ms |
5824 KB |
Output is correct |
7 |
Correct |
5 ms |
5964 KB |
Output is correct |
8 |
Correct |
6 ms |
5964 KB |
Output is correct |
9 |
Correct |
5 ms |
5836 KB |
Output is correct |
10 |
Correct |
12 ms |
7500 KB |
Output is correct |
11 |
Correct |
4 ms |
5836 KB |
Output is correct |
12 |
Correct |
5 ms |
5840 KB |
Output is correct |
13 |
Correct |
4 ms |
5836 KB |
Output is correct |
14 |
Correct |
4 ms |
5836 KB |
Output is correct |
15 |
Correct |
4 ms |
5836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
23112 KB |
Output is correct |
2 |
Correct |
334 ms |
22172 KB |
Output is correct |
3 |
Correct |
345 ms |
24628 KB |
Output is correct |
4 |
Correct |
321 ms |
22996 KB |
Output is correct |
5 |
Correct |
340 ms |
23024 KB |
Output is correct |
6 |
Correct |
337 ms |
23252 KB |
Output is correct |
7 |
Correct |
354 ms |
23316 KB |
Output is correct |
8 |
Correct |
332 ms |
22940 KB |
Output is correct |
9 |
Correct |
332 ms |
22392 KB |
Output is correct |
10 |
Correct |
287 ms |
22312 KB |
Output is correct |
11 |
Correct |
128 ms |
15676 KB |
Output is correct |
12 |
Correct |
354 ms |
22216 KB |
Output is correct |
13 |
Correct |
351 ms |
22332 KB |
Output is correct |
14 |
Correct |
354 ms |
22384 KB |
Output is correct |
15 |
Correct |
348 ms |
22076 KB |
Output is correct |
16 |
Correct |
353 ms |
22144 KB |
Output is correct |
17 |
Correct |
361 ms |
22872 KB |
Output is correct |
18 |
Correct |
337 ms |
23356 KB |
Output is correct |
19 |
Correct |
374 ms |
24280 KB |
Output is correct |
20 |
Correct |
349 ms |
22356 KB |
Output is correct |
21 |
Correct |
372 ms |
22908 KB |
Output is correct |
22 |
Correct |
348 ms |
22116 KB |
Output is correct |
23 |
Correct |
147 ms |
15804 KB |
Output is correct |
24 |
Correct |
347 ms |
23648 KB |
Output is correct |
25 |
Correct |
11 ms |
7500 KB |
Output is correct |
26 |
Correct |
4 ms |
5836 KB |
Output is correct |
27 |
Correct |
4 ms |
5820 KB |
Output is correct |
28 |
Correct |
18 ms |
9280 KB |
Output is correct |
29 |
Correct |
12 ms |
7500 KB |
Output is correct |
30 |
Correct |
4 ms |
5824 KB |
Output is correct |
31 |
Correct |
5 ms |
5964 KB |
Output is correct |
32 |
Correct |
6 ms |
5964 KB |
Output is correct |
33 |
Correct |
5 ms |
5836 KB |
Output is correct |
34 |
Correct |
12 ms |
7500 KB |
Output is correct |
35 |
Correct |
4 ms |
5836 KB |
Output is correct |
36 |
Correct |
5 ms |
5840 KB |
Output is correct |
37 |
Correct |
4 ms |
5836 KB |
Output is correct |
38 |
Correct |
4 ms |
5836 KB |
Output is correct |
39 |
Correct |
4 ms |
5836 KB |
Output is correct |
40 |
Correct |
313 ms |
23068 KB |
Output is correct |
41 |
Correct |
382 ms |
22444 KB |
Output is correct |
42 |
Correct |
341 ms |
22304 KB |
Output is correct |
43 |
Correct |
170 ms |
16980 KB |
Output is correct |
44 |
Correct |
152 ms |
16868 KB |
Output is correct |
45 |
Correct |
320 ms |
24220 KB |
Output is correct |
46 |
Correct |
371 ms |
23972 KB |
Output is correct |
47 |
Correct |
352 ms |
22984 KB |
Output is correct |
48 |
Correct |
176 ms |
16312 KB |
Output is correct |
49 |
Correct |
280 ms |
22720 KB |
Output is correct |
50 |
Correct |
406 ms |
24496 KB |
Output is correct |
51 |
Correct |
322 ms |
24204 KB |
Output is correct |