#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct A{
long long a,w,p;
bool operator<(const A& o)const{
return w>o.w;
}
};
long long ans;
vector<vector<long long>> dis(2,vector<long long>(N,1e18));
vector<A> g[N];
priority_queue<A> q;
bitset<N> vis;
void dijk(int idx,int s){
q.push({s,0});
dis[idx][s]=0;
while(!q.empty()){
auto [a,w,p]=q.top();
q.pop();
if(w>dis[idx][a])continue;
for(auto x:g[a]){
if(w+x.w<dis[idx][x.a])q.push({x.a,w+x.w}),dis[idx][x.a]=w+x.w;
}
}
}
void dijk2(int s,int e){
vector<long long> diss(N,1e18);
vector<vector<long long>> dp(2,vector<long long>(N,1e18));
vis=0;
q.push({s,0,0});
while(!q.empty()){
auto [a,w,p]=q.top();
q.pop();
if(!vis[a]){
vis[a]=true;
diss[a]=w;
dp[0][a]=min(dis[0][a],dp[0][p]);
dp[1][a]=min(dis[1][a],dp[1][p]);
for(auto x:g[a])q.push({x.a,w+x.w,a});
}
else if(w==diss[a]&&min(dis[0][a],dp[0][p])+min(dis[1][a],dp[1][p])<dp[0][a]+dp[1][a])dp[0][a]=min(dis[0][a],dp[0][p]),dp[1][a]=min(dis[1][a],dp[1][p]);
}
ans=min(ans,dp[0][e]+dp[1][e]);
}
int main(){
int n,m,s,t,u,v,i,a,b;
long long w,mi;
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
for(i=1;i<=m;i++){
scanf("%d %d %lld",&a,&b,&w);
g[a].push_back({b,w});
g[b].push_back({a,w});
}
dijk(0,u);
dijk(1,v);
ans=dis[0][v];
dijk2(s,t);
dijk2(t,s);
printf("%lld",ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:17: warning: unused variable 'mi' [-Wunused-variable]
53 | long long w,mi;
| ^~
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %lld",&a,&b,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
28080 KB |
Output is correct |
2 |
Correct |
422 ms |
28136 KB |
Output is correct |
3 |
Correct |
422 ms |
28112 KB |
Output is correct |
4 |
Correct |
471 ms |
28036 KB |
Output is correct |
5 |
Correct |
409 ms |
25080 KB |
Output is correct |
6 |
Correct |
500 ms |
27968 KB |
Output is correct |
7 |
Correct |
420 ms |
28084 KB |
Output is correct |
8 |
Correct |
445 ms |
28088 KB |
Output is correct |
9 |
Correct |
465 ms |
28148 KB |
Output is correct |
10 |
Correct |
363 ms |
28048 KB |
Output is correct |
11 |
Correct |
144 ms |
13828 KB |
Output is correct |
12 |
Correct |
462 ms |
28212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
450 ms |
28172 KB |
Output is correct |
2 |
Correct |
450 ms |
25120 KB |
Output is correct |
3 |
Correct |
432 ms |
28336 KB |
Output is correct |
4 |
Correct |
421 ms |
25140 KB |
Output is correct |
5 |
Correct |
427 ms |
25196 KB |
Output is correct |
6 |
Correct |
425 ms |
28028 KB |
Output is correct |
7 |
Correct |
430 ms |
25000 KB |
Output is correct |
8 |
Correct |
425 ms |
25140 KB |
Output is correct |
9 |
Correct |
447 ms |
25108 KB |
Output is correct |
10 |
Correct |
433 ms |
28288 KB |
Output is correct |
11 |
Correct |
139 ms |
14004 KB |
Output is correct |
12 |
Correct |
417 ms |
28160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
10084 KB |
Output is correct |
2 |
Correct |
5 ms |
7364 KB |
Output is correct |
3 |
Correct |
5 ms |
7364 KB |
Output is correct |
4 |
Correct |
48 ms |
13320 KB |
Output is correct |
5 |
Correct |
26 ms |
10948 KB |
Output is correct |
6 |
Correct |
6 ms |
7536 KB |
Output is correct |
7 |
Correct |
6 ms |
7748 KB |
Output is correct |
8 |
Correct |
9 ms |
7724 KB |
Output is correct |
9 |
Correct |
6 ms |
7556 KB |
Output is correct |
10 |
Correct |
23 ms |
11104 KB |
Output is correct |
11 |
Correct |
5 ms |
7364 KB |
Output is correct |
12 |
Correct |
5 ms |
7364 KB |
Output is correct |
13 |
Correct |
5 ms |
7364 KB |
Output is correct |
14 |
Correct |
5 ms |
7488 KB |
Output is correct |
15 |
Correct |
5 ms |
7488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
468 ms |
28080 KB |
Output is correct |
2 |
Correct |
422 ms |
28136 KB |
Output is correct |
3 |
Correct |
422 ms |
28112 KB |
Output is correct |
4 |
Correct |
471 ms |
28036 KB |
Output is correct |
5 |
Correct |
409 ms |
25080 KB |
Output is correct |
6 |
Correct |
500 ms |
27968 KB |
Output is correct |
7 |
Correct |
420 ms |
28084 KB |
Output is correct |
8 |
Correct |
445 ms |
28088 KB |
Output is correct |
9 |
Correct |
465 ms |
28148 KB |
Output is correct |
10 |
Correct |
363 ms |
28048 KB |
Output is correct |
11 |
Correct |
144 ms |
13828 KB |
Output is correct |
12 |
Correct |
462 ms |
28212 KB |
Output is correct |
13 |
Correct |
450 ms |
28172 KB |
Output is correct |
14 |
Correct |
450 ms |
25120 KB |
Output is correct |
15 |
Correct |
432 ms |
28336 KB |
Output is correct |
16 |
Correct |
421 ms |
25140 KB |
Output is correct |
17 |
Correct |
427 ms |
25196 KB |
Output is correct |
18 |
Correct |
425 ms |
28028 KB |
Output is correct |
19 |
Correct |
430 ms |
25000 KB |
Output is correct |
20 |
Correct |
425 ms |
25140 KB |
Output is correct |
21 |
Correct |
447 ms |
25108 KB |
Output is correct |
22 |
Correct |
433 ms |
28288 KB |
Output is correct |
23 |
Correct |
139 ms |
14004 KB |
Output is correct |
24 |
Correct |
417 ms |
28160 KB |
Output is correct |
25 |
Correct |
23 ms |
10084 KB |
Output is correct |
26 |
Correct |
5 ms |
7364 KB |
Output is correct |
27 |
Correct |
5 ms |
7364 KB |
Output is correct |
28 |
Correct |
48 ms |
13320 KB |
Output is correct |
29 |
Correct |
26 ms |
10948 KB |
Output is correct |
30 |
Correct |
6 ms |
7536 KB |
Output is correct |
31 |
Correct |
6 ms |
7748 KB |
Output is correct |
32 |
Correct |
9 ms |
7724 KB |
Output is correct |
33 |
Correct |
6 ms |
7556 KB |
Output is correct |
34 |
Correct |
23 ms |
11104 KB |
Output is correct |
35 |
Correct |
5 ms |
7364 KB |
Output is correct |
36 |
Correct |
5 ms |
7364 KB |
Output is correct |
37 |
Correct |
5 ms |
7364 KB |
Output is correct |
38 |
Correct |
5 ms |
7488 KB |
Output is correct |
39 |
Correct |
5 ms |
7488 KB |
Output is correct |
40 |
Correct |
470 ms |
26792 KB |
Output is correct |
41 |
Correct |
478 ms |
27952 KB |
Output is correct |
42 |
Correct |
501 ms |
28152 KB |
Output is correct |
43 |
Correct |
137 ms |
13840 KB |
Output is correct |
44 |
Correct |
144 ms |
13948 KB |
Output is correct |
45 |
Correct |
400 ms |
25016 KB |
Output is correct |
46 |
Correct |
404 ms |
24976 KB |
Output is correct |
47 |
Correct |
458 ms |
24692 KB |
Output is correct |
48 |
Correct |
144 ms |
13920 KB |
Output is correct |
49 |
Correct |
436 ms |
26616 KB |
Output is correct |
50 |
Correct |
423 ms |
25140 KB |
Output is correct |
51 |
Correct |
396 ms |
25036 KB |
Output is correct |