#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define MAXM 200005
typedef long long lint;
typedef pair<lint, int> pli;
const lint LINF = 1ll << 50;
int N, M, S, T, U, V;
int A[MAXM], B[MAXM];
lint C[MAXM];
vector<pli> ed[MAXN];
priority_queue<pli, vector<pli>, greater<pli> > pq;
lint disS[MAXN], disT[MAXN], disU[MAXN], disV[MAXN];
vector<int> sho;
lint dp[MAXN];
lint ans;
void dij(int x, lint dis[]) {
pq.push(make_pair(0ll, x));
for(int i = 1; i <= N; i++) dis[i] = LINF;
dis[x] = 0ll;
while(!pq.empty()) {
pli t = pq.top();
pq.pop();
if(dis[t.second] != t.first) continue;
for(auto a : ed[t.second]) if(t.first + a.first < dis[a.second]) {
dis[a.second] = t.first + a.first;
pq.push(make_pair(dis[a.second], a.second));
}
}
}
void solve(int U, int V, lint disU[], lint disV[]) {
for(auto a : sho) {
dp[a] = disU[a];
for(auto b : ed[a]) if(disS[b.second] + disT[b.second] == disS[T] && disS[b.second] < disS[a])
dp[a] = min(dp[a], dp[b.second]);
ans = min(ans, dp[a] + disV[a]);
}
}
int main() {
scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
for(int i = 0; i < M; i++) scanf("%d%d%lld", A + i, B + i, C + i);
for(int i = 0; i < M; i++) {
ed[A[i]].push_back(make_pair(C[i], B[i]));
ed[B[i]].push_back(make_pair(C[i], A[i]));
}
dij(S, disS);
dij(T, disT);
dij(U, disU);
dij(V, disV);
for(int i = 1; i <= N; i++) if(disS[i] + disT[i] == disS[T]) sho.push_back(i);
sort(sho.begin(), sho.end(), [&](const int &a, const int &b) { return disS[a] < disS[b]; } );
ans = disU[V];
solve(U, V, disU, disV);
solve(V, U, disV, disU);
printf("%lld", ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51: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:52:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < M; i++) scanf("%d%d%lld", A + i, B + i, C + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
20620 KB |
Output is correct |
2 |
Correct |
391 ms |
21280 KB |
Output is correct |
3 |
Correct |
429 ms |
22012 KB |
Output is correct |
4 |
Correct |
367 ms |
21580 KB |
Output is correct |
5 |
Correct |
380 ms |
21352 KB |
Output is correct |
6 |
Correct |
385 ms |
20708 KB |
Output is correct |
7 |
Correct |
402 ms |
21500 KB |
Output is correct |
8 |
Correct |
410 ms |
21608 KB |
Output is correct |
9 |
Correct |
384 ms |
20336 KB |
Output is correct |
10 |
Correct |
319 ms |
20072 KB |
Output is correct |
11 |
Correct |
153 ms |
13652 KB |
Output is correct |
12 |
Correct |
398 ms |
20280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
409 ms |
21500 KB |
Output is correct |
2 |
Correct |
408 ms |
21552 KB |
Output is correct |
3 |
Correct |
415 ms |
21232 KB |
Output is correct |
4 |
Correct |
433 ms |
21480 KB |
Output is correct |
5 |
Correct |
399 ms |
21480 KB |
Output is correct |
6 |
Correct |
399 ms |
21644 KB |
Output is correct |
7 |
Correct |
409 ms |
21736 KB |
Output is correct |
8 |
Correct |
420 ms |
21520 KB |
Output is correct |
9 |
Correct |
416 ms |
21388 KB |
Output is correct |
10 |
Correct |
423 ms |
21300 KB |
Output is correct |
11 |
Correct |
176 ms |
13684 KB |
Output is correct |
12 |
Correct |
416 ms |
21672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
4344 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
4 ms |
2812 KB |
Output is correct |
4 |
Correct |
25 ms |
6008 KB |
Output is correct |
5 |
Correct |
15 ms |
4344 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
5 ms |
2808 KB |
Output is correct |
8 |
Correct |
6 ms |
2936 KB |
Output is correct |
9 |
Correct |
5 ms |
2812 KB |
Output is correct |
10 |
Correct |
15 ms |
4344 KB |
Output is correct |
11 |
Correct |
4 ms |
2676 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
4 ms |
2680 KB |
Output is correct |
14 |
Correct |
5 ms |
2808 KB |
Output is correct |
15 |
Correct |
4 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
20620 KB |
Output is correct |
2 |
Correct |
391 ms |
21280 KB |
Output is correct |
3 |
Correct |
429 ms |
22012 KB |
Output is correct |
4 |
Correct |
367 ms |
21580 KB |
Output is correct |
5 |
Correct |
380 ms |
21352 KB |
Output is correct |
6 |
Correct |
385 ms |
20708 KB |
Output is correct |
7 |
Correct |
402 ms |
21500 KB |
Output is correct |
8 |
Correct |
410 ms |
21608 KB |
Output is correct |
9 |
Correct |
384 ms |
20336 KB |
Output is correct |
10 |
Correct |
319 ms |
20072 KB |
Output is correct |
11 |
Correct |
153 ms |
13652 KB |
Output is correct |
12 |
Correct |
398 ms |
20280 KB |
Output is correct |
13 |
Correct |
409 ms |
21500 KB |
Output is correct |
14 |
Correct |
408 ms |
21552 KB |
Output is correct |
15 |
Correct |
415 ms |
21232 KB |
Output is correct |
16 |
Correct |
433 ms |
21480 KB |
Output is correct |
17 |
Correct |
399 ms |
21480 KB |
Output is correct |
18 |
Correct |
399 ms |
21644 KB |
Output is correct |
19 |
Correct |
409 ms |
21736 KB |
Output is correct |
20 |
Correct |
420 ms |
21520 KB |
Output is correct |
21 |
Correct |
416 ms |
21388 KB |
Output is correct |
22 |
Correct |
423 ms |
21300 KB |
Output is correct |
23 |
Correct |
176 ms |
13684 KB |
Output is correct |
24 |
Correct |
416 ms |
21672 KB |
Output is correct |
25 |
Correct |
15 ms |
4344 KB |
Output is correct |
26 |
Correct |
5 ms |
2808 KB |
Output is correct |
27 |
Correct |
4 ms |
2812 KB |
Output is correct |
28 |
Correct |
25 ms |
6008 KB |
Output is correct |
29 |
Correct |
15 ms |
4344 KB |
Output is correct |
30 |
Correct |
5 ms |
2808 KB |
Output is correct |
31 |
Correct |
5 ms |
2808 KB |
Output is correct |
32 |
Correct |
6 ms |
2936 KB |
Output is correct |
33 |
Correct |
5 ms |
2812 KB |
Output is correct |
34 |
Correct |
15 ms |
4344 KB |
Output is correct |
35 |
Correct |
4 ms |
2676 KB |
Output is correct |
36 |
Correct |
4 ms |
2680 KB |
Output is correct |
37 |
Correct |
4 ms |
2680 KB |
Output is correct |
38 |
Correct |
5 ms |
2808 KB |
Output is correct |
39 |
Correct |
4 ms |
2808 KB |
Output is correct |
40 |
Correct |
359 ms |
20200 KB |
Output is correct |
41 |
Correct |
381 ms |
20460 KB |
Output is correct |
42 |
Correct |
386 ms |
20528 KB |
Output is correct |
43 |
Correct |
165 ms |
13808 KB |
Output is correct |
44 |
Correct |
181 ms |
13980 KB |
Output is correct |
45 |
Correct |
383 ms |
21756 KB |
Output is correct |
46 |
Correct |
366 ms |
21612 KB |
Output is correct |
47 |
Correct |
384 ms |
21232 KB |
Output is correct |
48 |
Correct |
169 ms |
13936 KB |
Output is correct |
49 |
Correct |
344 ms |
20356 KB |
Output is correct |
50 |
Correct |
411 ms |
21704 KB |
Output is correct |
51 |
Correct |
419 ms |
21612 KB |
Output is correct |