#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 100005;
vector<pi> gph[MAXN];
int a[4], n, m;
lint dist[4][MAXN];
void dijkstra(lint* d, int x){
priority_queue<pi, vector<pi>, greater<pi> > pq;
pq.push(pi(0, x));
d[x] = 0;
while(!pq.empty()){
auto p = pq.top();
pq.pop();
if(d[p.second] != p.first) continue;
for(auto &i : gph[p.second]){
if(d[i.second] > p.first + i.first){
d[i.second] = p.first + i.first;
pq.push(pi(d[i.second], i.second));
}
}
}
}
lint dp[MAXN];
int ord[MAXN];
lint solve(int v, int w){
iota(ord, ord + n + 1, 0);
memset(dp, 0, sizeof(dp));
sort(ord + 1, ord + n + 1, [&](const int &p, const int &q){
return dist[v][p] < dist[v][q];
});
lint ans = 1e18;
for(int i=n; i; i--){
int x = ord[i];
dp[x] = dist[3][x];
for(auto &j : gph[x]){
if(dist[v][x] + j.first + dist[w][j.second] == dist[v][a[w]]){
dp[x] = min(dp[x], dp[j.second]);
}
}
ans = min(ans, dp[x] + dist[2][x]);
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<4; i++) scanf("%d",&a[i]);
for(int i=0; i<m; i++){
int s, e, x;
scanf("%d %d %d",&s,&e,&x);
gph[s].push_back(pi(x, e));
gph[e].push_back(pi(x, s));
}
memset(dist, 0x3f, sizeof(dist));
for(int i=0; i<4; i++) dijkstra(dist[i], a[i]);
cout << min({solve(0, 1), solve(1, 0), dist[2][a[3]]}) << endl;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
commuter_pass.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<4; i++) scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
commuter_pass.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
433 ms |
19920 KB |
Output is correct |
2 |
Correct |
437 ms |
18768 KB |
Output is correct |
3 |
Correct |
478 ms |
19848 KB |
Output is correct |
4 |
Correct |
419 ms |
19780 KB |
Output is correct |
5 |
Correct |
428 ms |
18780 KB |
Output is correct |
6 |
Correct |
445 ms |
20208 KB |
Output is correct |
7 |
Correct |
430 ms |
18744 KB |
Output is correct |
8 |
Correct |
445 ms |
18708 KB |
Output is correct |
9 |
Correct |
430 ms |
18772 KB |
Output is correct |
10 |
Correct |
360 ms |
18392 KB |
Output is correct |
11 |
Correct |
188 ms |
12808 KB |
Output is correct |
12 |
Correct |
444 ms |
18744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
18820 KB |
Output is correct |
2 |
Correct |
469 ms |
18832 KB |
Output is correct |
3 |
Correct |
449 ms |
18804 KB |
Output is correct |
4 |
Correct |
457 ms |
18728 KB |
Output is correct |
5 |
Correct |
507 ms |
18788 KB |
Output is correct |
6 |
Correct |
439 ms |
18716 KB |
Output is correct |
7 |
Correct |
466 ms |
18700 KB |
Output is correct |
8 |
Correct |
464 ms |
18732 KB |
Output is correct |
9 |
Correct |
495 ms |
18916 KB |
Output is correct |
10 |
Correct |
504 ms |
18760 KB |
Output is correct |
11 |
Correct |
192 ms |
12772 KB |
Output is correct |
12 |
Correct |
447 ms |
18800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8312 KB |
Output is correct |
2 |
Correct |
8 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6648 KB |
Output is correct |
4 |
Correct |
29 ms |
10048 KB |
Output is correct |
5 |
Correct |
18 ms |
8312 KB |
Output is correct |
6 |
Correct |
8 ms |
6648 KB |
Output is correct |
7 |
Correct |
9 ms |
6776 KB |
Output is correct |
8 |
Correct |
10 ms |
6776 KB |
Output is correct |
9 |
Correct |
8 ms |
6740 KB |
Output is correct |
10 |
Correct |
18 ms |
8312 KB |
Output is correct |
11 |
Correct |
9 ms |
6648 KB |
Output is correct |
12 |
Correct |
8 ms |
6648 KB |
Output is correct |
13 |
Correct |
10 ms |
6648 KB |
Output is correct |
14 |
Correct |
8 ms |
6648 KB |
Output is correct |
15 |
Correct |
8 ms |
6648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
433 ms |
19920 KB |
Output is correct |
2 |
Correct |
437 ms |
18768 KB |
Output is correct |
3 |
Correct |
478 ms |
19848 KB |
Output is correct |
4 |
Correct |
419 ms |
19780 KB |
Output is correct |
5 |
Correct |
428 ms |
18780 KB |
Output is correct |
6 |
Correct |
445 ms |
20208 KB |
Output is correct |
7 |
Correct |
430 ms |
18744 KB |
Output is correct |
8 |
Correct |
445 ms |
18708 KB |
Output is correct |
9 |
Correct |
430 ms |
18772 KB |
Output is correct |
10 |
Correct |
360 ms |
18392 KB |
Output is correct |
11 |
Correct |
188 ms |
12808 KB |
Output is correct |
12 |
Correct |
444 ms |
18744 KB |
Output is correct |
13 |
Correct |
451 ms |
18820 KB |
Output is correct |
14 |
Correct |
469 ms |
18832 KB |
Output is correct |
15 |
Correct |
449 ms |
18804 KB |
Output is correct |
16 |
Correct |
457 ms |
18728 KB |
Output is correct |
17 |
Correct |
507 ms |
18788 KB |
Output is correct |
18 |
Correct |
439 ms |
18716 KB |
Output is correct |
19 |
Correct |
466 ms |
18700 KB |
Output is correct |
20 |
Correct |
464 ms |
18732 KB |
Output is correct |
21 |
Correct |
495 ms |
18916 KB |
Output is correct |
22 |
Correct |
504 ms |
18760 KB |
Output is correct |
23 |
Correct |
192 ms |
12772 KB |
Output is correct |
24 |
Correct |
447 ms |
18800 KB |
Output is correct |
25 |
Correct |
18 ms |
8312 KB |
Output is correct |
26 |
Correct |
8 ms |
6648 KB |
Output is correct |
27 |
Correct |
8 ms |
6648 KB |
Output is correct |
28 |
Correct |
29 ms |
10048 KB |
Output is correct |
29 |
Correct |
18 ms |
8312 KB |
Output is correct |
30 |
Correct |
8 ms |
6648 KB |
Output is correct |
31 |
Correct |
9 ms |
6776 KB |
Output is correct |
32 |
Correct |
10 ms |
6776 KB |
Output is correct |
33 |
Correct |
8 ms |
6740 KB |
Output is correct |
34 |
Correct |
18 ms |
8312 KB |
Output is correct |
35 |
Correct |
9 ms |
6648 KB |
Output is correct |
36 |
Correct |
8 ms |
6648 KB |
Output is correct |
37 |
Correct |
10 ms |
6648 KB |
Output is correct |
38 |
Correct |
8 ms |
6648 KB |
Output is correct |
39 |
Correct |
8 ms |
6648 KB |
Output is correct |
40 |
Correct |
424 ms |
19864 KB |
Output is correct |
41 |
Correct |
440 ms |
19072 KB |
Output is correct |
42 |
Correct |
456 ms |
19044 KB |
Output is correct |
43 |
Correct |
194 ms |
13280 KB |
Output is correct |
44 |
Correct |
187 ms |
13076 KB |
Output is correct |
45 |
Correct |
387 ms |
19168 KB |
Output is correct |
46 |
Correct |
414 ms |
18652 KB |
Output is correct |
47 |
Correct |
444 ms |
20148 KB |
Output is correct |
48 |
Correct |
206 ms |
13048 KB |
Output is correct |
49 |
Correct |
377 ms |
19800 KB |
Output is correct |
50 |
Correct |
422 ms |
18812 KB |
Output is correct |
51 |
Correct |
471 ms |
18696 KB |
Output is correct |