#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p2;
const int N=1e5+5;
const ll inf=1e18;
int n,m,s,t,ss,tt;
vector<pair<int,int>> adj[N];
vector<ll> dist1(N,inf),dist2(N,inf),dist3(N,inf);
ll ans;
ll dp1[N],dp2[N];
bool vis[N];
void dijk(int st,vector<ll> &dist){
priority_queue<p2,vector<p2>,greater<p2>> pq;
vector<bool> vis(N);
dist[st]=0;
pq.emplace(0,st);
while(!pq.empty()){
auto [d,u]=pq.top();
pq.pop();
if(vis[u])continue;
vis[u]=true;
for(auto [v,w]:adj[u]){
if(d+w>=dist[v])continue;
dist[v]=d+w;
pq.emplace(d+w,v);
}
}
}
void dfs(int u){
if(vis[u])return;
vis[u]=true;
dp1[u]=dist1[u];
dp2[u]=dist2[u];
for(auto [v,w]:adj[u]){
if(dist3[v]+w!=dist3[u])continue;
dfs(v);
dp1[u]=min(dp1[u],dp1[v]);
dp2[u]=min(dp2[u],dp2[v]);
}
ans=min(ans,dp1[u]+dist2[u]);
ans=min(ans,dp2[u]+dist1[u]);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> s >> t >> ss >> tt;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
dijk(ss,dist1);
dijk(tt,dist2);
dijk(s,dist3);
ans=dist1[tt];
dfs(t);
cout << ans << "\n";
}
Compilation message
commuter_pass.cpp: In function 'void dijk(int, std::vector<long long int>&)':
commuter_pass.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | auto [d,u]=pq.top();
| ^
commuter_pass.cpp:28:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto [v,w]:adj[u]){
| ^
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for(auto [v,w]:adj[u]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
18236 KB |
Output is correct |
2 |
Correct |
142 ms |
16764 KB |
Output is correct |
3 |
Correct |
158 ms |
21988 KB |
Output is correct |
4 |
Correct |
212 ms |
18172 KB |
Output is correct |
5 |
Correct |
158 ms |
16544 KB |
Output is correct |
6 |
Correct |
220 ms |
18384 KB |
Output is correct |
7 |
Correct |
172 ms |
16624 KB |
Output is correct |
8 |
Correct |
142 ms |
16684 KB |
Output is correct |
9 |
Correct |
140 ms |
17444 KB |
Output is correct |
10 |
Correct |
124 ms |
17420 KB |
Output is correct |
11 |
Correct |
83 ms |
15036 KB |
Output is correct |
12 |
Correct |
164 ms |
17336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
18820 KB |
Output is correct |
2 |
Correct |
186 ms |
18992 KB |
Output is correct |
3 |
Correct |
178 ms |
18604 KB |
Output is correct |
4 |
Correct |
173 ms |
18868 KB |
Output is correct |
5 |
Correct |
159 ms |
19476 KB |
Output is correct |
6 |
Correct |
192 ms |
21456 KB |
Output is correct |
7 |
Correct |
198 ms |
21656 KB |
Output is correct |
8 |
Correct |
200 ms |
19008 KB |
Output is correct |
9 |
Correct |
217 ms |
19384 KB |
Output is correct |
10 |
Correct |
174 ms |
18648 KB |
Output is correct |
11 |
Correct |
54 ms |
16772 KB |
Output is correct |
12 |
Correct |
181 ms |
21700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6100 KB |
Output is correct |
2 |
Correct |
3 ms |
5052 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
16 ms |
7128 KB |
Output is correct |
5 |
Correct |
10 ms |
6100 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
3 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
10 ms |
6060 KB |
Output is correct |
11 |
Correct |
3 ms |
5048 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5056 KB |
Output is correct |
15 |
Correct |
2 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
18236 KB |
Output is correct |
2 |
Correct |
142 ms |
16764 KB |
Output is correct |
3 |
Correct |
158 ms |
21988 KB |
Output is correct |
4 |
Correct |
212 ms |
18172 KB |
Output is correct |
5 |
Correct |
158 ms |
16544 KB |
Output is correct |
6 |
Correct |
220 ms |
18384 KB |
Output is correct |
7 |
Correct |
172 ms |
16624 KB |
Output is correct |
8 |
Correct |
142 ms |
16684 KB |
Output is correct |
9 |
Correct |
140 ms |
17444 KB |
Output is correct |
10 |
Correct |
124 ms |
17420 KB |
Output is correct |
11 |
Correct |
83 ms |
15036 KB |
Output is correct |
12 |
Correct |
164 ms |
17336 KB |
Output is correct |
13 |
Correct |
164 ms |
18820 KB |
Output is correct |
14 |
Correct |
186 ms |
18992 KB |
Output is correct |
15 |
Correct |
178 ms |
18604 KB |
Output is correct |
16 |
Correct |
173 ms |
18868 KB |
Output is correct |
17 |
Correct |
159 ms |
19476 KB |
Output is correct |
18 |
Correct |
192 ms |
21456 KB |
Output is correct |
19 |
Correct |
198 ms |
21656 KB |
Output is correct |
20 |
Correct |
200 ms |
19008 KB |
Output is correct |
21 |
Correct |
217 ms |
19384 KB |
Output is correct |
22 |
Correct |
174 ms |
18648 KB |
Output is correct |
23 |
Correct |
54 ms |
16772 KB |
Output is correct |
24 |
Correct |
181 ms |
21700 KB |
Output is correct |
25 |
Correct |
7 ms |
6100 KB |
Output is correct |
26 |
Correct |
3 ms |
5052 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
16 ms |
7128 KB |
Output is correct |
29 |
Correct |
10 ms |
6100 KB |
Output is correct |
30 |
Correct |
3 ms |
5076 KB |
Output is correct |
31 |
Correct |
3 ms |
5204 KB |
Output is correct |
32 |
Correct |
4 ms |
5204 KB |
Output is correct |
33 |
Correct |
4 ms |
5076 KB |
Output is correct |
34 |
Correct |
10 ms |
6060 KB |
Output is correct |
35 |
Correct |
3 ms |
5048 KB |
Output is correct |
36 |
Correct |
2 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5076 KB |
Output is correct |
38 |
Correct |
3 ms |
5056 KB |
Output is correct |
39 |
Correct |
2 ms |
5076 KB |
Output is correct |
40 |
Correct |
144 ms |
18700 KB |
Output is correct |
41 |
Correct |
156 ms |
17416 KB |
Output is correct |
42 |
Correct |
183 ms |
17452 KB |
Output is correct |
43 |
Correct |
60 ms |
15792 KB |
Output is correct |
44 |
Correct |
77 ms |
15764 KB |
Output is correct |
45 |
Correct |
163 ms |
16468 KB |
Output is correct |
46 |
Correct |
155 ms |
16208 KB |
Output is correct |
47 |
Correct |
151 ms |
18120 KB |
Output is correct |
48 |
Correct |
62 ms |
12748 KB |
Output is correct |
49 |
Correct |
157 ms |
18300 KB |
Output is correct |
50 |
Correct |
174 ms |
16580 KB |
Output is correct |
51 |
Correct |
166 ms |
16552 KB |
Output is correct |