#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define int long long
#define pii pair<int,int>
int par(int a,vector<int>& id){
if(id[a]==a)return a;
return id[a]=par(id[a],id);
}
void unite(int a,int b,vector<int>& id){
a=par(a,id),b=par(b,id);
id[a]=b;
}
void nodijkstra(int a,int b,vector<vector<pii>>& p,vector<int>& dist,vector<int>& distu,vector<int>& distv,int s,int t){
queue<int> q;
vector<vector<int>> g(p.size(),vector<int>());
q.push(a);
vector<bool> seen(g.size(),false);
while(!q.empty()){
int u=q.front();
seen[u]=true;
q.pop();
for(auto v:p[u]){
if(dist[v.first]+v.second==dist[u]){
g[u].push_back(v.first);
if(!seen[v.first])q.push(v.first);
}
}
}
int ans=distu[t],n=g.size();
vector<int> bestu(n),bestv(n),cnt(n),cnt2(n);
for(int i=0;i<n;i++)for(auto v:g[i]){
cnt[v]++;
cnt2[v]++;
}
for(int i=0;i<n;i++){
bestu[i]=distu[i];
bestv[i]=distv[i];
}
q.push(a);
while(!q.empty()){
int u=q.front();
//cout<<u<<' ';
ans=min(ans,bestu[u]+distv[u]);
q.pop();
for(auto v:g[u]){
cnt[v]--;
bestu[v]=min(bestu[v],bestu[u]);
if(!cnt[v])q.push(v);
}
}
q.push(a);
while(!q.empty()){
int u=q.front();
ans=min(ans,bestv[u]+distu[u]);
q.pop();
for(auto v:g[u]){
cnt2[v]--;
bestv[v]=min(bestv[v],bestv[u]);
if(!cnt2[v])q.push(v);
}
}
cout<<ans<<'\n';
}
void dijkstra2(int s,int t,vector<vector<pii>>& g,int a,int b,vector<int>& dist){
priority_queue<pii> pqu,pqv;
vector<int> distu(g.size(),1e18),distv(g.size(),1e18);
pqu.push({0,s});
distu[s]=0;
while(!pqu.empty()){
int u=pqu.top().second,d=-pqu.top().first;
pqu.pop();
if(d>distu[u])continue;
for(auto v:g[u]){
if(distu[v.first]>distu[u]+v.second){
distu[v.first]=distu[u]+v.second;
pqu.push({-distu[v.first],v.first});
}
}
}
pqv.push({0,t});
distv[t]=0;
while(!pqv.empty()){
int u=pqv.top().second,d=-pqv.top().first;
pqv.pop();
if(d>distv[u])continue;
for(auto v:g[u]){
if(distv[v.first]>distv[u]+v.second){
distv[v.first]=distv[u]+v.second;
pqv.push({-distv[v.first],v.first});
}
}
}
int ans=1e18,n=g.size();
//vector<pii> distid(n,{1e18,1e18});
nodijkstra(b,a,g,dist,distu,distv,s,t);
/*for(int i=0;i<n;i++){
cout<<id[i]<<' ';
ans=min(ans,distid[i].first+distid[i].second);
}
cout<<ans<<'\n';*/
}
void dijkstra(int a,int b,vector<vector<pii>>& g,int s,int t){
priority_queue<pii> pq;
vector<int> dist(g.size(),1e18);
pq.push({0,a});
dist[a]=0;
while(!pq.empty()){
int u=pq.top().second,d=-pq.top().first;
pq.pop();
if(d>dist[u])continue;
for(auto v:g[u]){
if(dist[v.first]>dist[u]+v.second){
dist[v.first]=dist[u]+v.second;
pq.push({-dist[v.first],v.first});
}
}
}
//vector<int> id=nodijkstra(b,a,g,dist);
//for(int i=0;i<g.size();i++)cout<<id[i]<<' ';
dijkstra2(s,t,g,a,b,dist);
}
signed main(){
int n,m,u,v,s,t,x,y,w;
cin>>n>>m>>s>>t>>u>>v;
s--;t--;u--;v--;
vector<vector<pii>> g(n,vector<pii>());
while(m--){
cin>>x>>y>>w;
x--;y--;
g[x].push_back({y,w});
g[y].push_back({x,w});
}
dijkstra(s,t,g,u,v);
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, long long int, long long int, std::vector<long long int>&)':
commuter_pass.cpp:95:9: warning: unused variable 'ans' [-Wunused-variable]
95 | int ans=1e18,n=g.size();
| ^~~
commuter_pass.cpp:95:18: warning: unused variable 'n' [-Wunused-variable]
95 | int ans=1e18,n=g.size();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
360 ms |
27816 KB |
Output is correct |
2 |
Correct |
348 ms |
27360 KB |
Output is correct |
3 |
Correct |
379 ms |
27924 KB |
Output is correct |
4 |
Correct |
347 ms |
27636 KB |
Output is correct |
5 |
Correct |
357 ms |
27652 KB |
Output is correct |
6 |
Correct |
383 ms |
28224 KB |
Output is correct |
7 |
Correct |
405 ms |
28260 KB |
Output is correct |
8 |
Correct |
368 ms |
28096 KB |
Output is correct |
9 |
Correct |
356 ms |
27652 KB |
Output is correct |
10 |
Correct |
428 ms |
27276 KB |
Output is correct |
11 |
Correct |
156 ms |
18764 KB |
Output is correct |
12 |
Correct |
355 ms |
27584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
27620 KB |
Output is correct |
2 |
Correct |
368 ms |
27236 KB |
Output is correct |
3 |
Correct |
362 ms |
26968 KB |
Output is correct |
4 |
Correct |
366 ms |
27148 KB |
Output is correct |
5 |
Correct |
367 ms |
27480 KB |
Output is correct |
6 |
Correct |
374 ms |
27896 KB |
Output is correct |
7 |
Correct |
396 ms |
28212 KB |
Output is correct |
8 |
Correct |
367 ms |
27136 KB |
Output is correct |
9 |
Correct |
387 ms |
27352 KB |
Output is correct |
10 |
Correct |
381 ms |
27204 KB |
Output is correct |
11 |
Correct |
181 ms |
19436 KB |
Output is correct |
12 |
Correct |
396 ms |
27868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
4652 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
40 ms |
3704 KB |
Output is correct |
5 |
Correct |
18 ms |
1972 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
444 KB |
Output is correct |
8 |
Correct |
3 ms |
564 KB |
Output is correct |
9 |
Correct |
2 ms |
440 KB |
Output is correct |
10 |
Correct |
20 ms |
2024 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
2 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
360 ms |
27816 KB |
Output is correct |
2 |
Correct |
348 ms |
27360 KB |
Output is correct |
3 |
Correct |
379 ms |
27924 KB |
Output is correct |
4 |
Correct |
347 ms |
27636 KB |
Output is correct |
5 |
Correct |
357 ms |
27652 KB |
Output is correct |
6 |
Correct |
383 ms |
28224 KB |
Output is correct |
7 |
Correct |
405 ms |
28260 KB |
Output is correct |
8 |
Correct |
368 ms |
28096 KB |
Output is correct |
9 |
Correct |
356 ms |
27652 KB |
Output is correct |
10 |
Correct |
428 ms |
27276 KB |
Output is correct |
11 |
Correct |
156 ms |
18764 KB |
Output is correct |
12 |
Correct |
355 ms |
27584 KB |
Output is correct |
13 |
Correct |
375 ms |
27620 KB |
Output is correct |
14 |
Correct |
368 ms |
27236 KB |
Output is correct |
15 |
Correct |
362 ms |
26968 KB |
Output is correct |
16 |
Correct |
366 ms |
27148 KB |
Output is correct |
17 |
Correct |
367 ms |
27480 KB |
Output is correct |
18 |
Correct |
374 ms |
27896 KB |
Output is correct |
19 |
Correct |
396 ms |
28212 KB |
Output is correct |
20 |
Correct |
367 ms |
27136 KB |
Output is correct |
21 |
Correct |
387 ms |
27352 KB |
Output is correct |
22 |
Correct |
381 ms |
27204 KB |
Output is correct |
23 |
Correct |
181 ms |
19436 KB |
Output is correct |
24 |
Correct |
396 ms |
27868 KB |
Output is correct |
25 |
Correct |
30 ms |
4652 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
304 KB |
Output is correct |
28 |
Correct |
40 ms |
3704 KB |
Output is correct |
29 |
Correct |
18 ms |
1972 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
444 KB |
Output is correct |
32 |
Correct |
3 ms |
564 KB |
Output is correct |
33 |
Correct |
2 ms |
440 KB |
Output is correct |
34 |
Correct |
20 ms |
2024 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
2 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
2 ms |
316 KB |
Output is correct |
40 |
Correct |
375 ms |
28776 KB |
Output is correct |
41 |
Correct |
368 ms |
27808 KB |
Output is correct |
42 |
Correct |
374 ms |
27800 KB |
Output is correct |
43 |
Correct |
232 ms |
20756 KB |
Output is correct |
44 |
Correct |
202 ms |
20656 KB |
Output is correct |
45 |
Correct |
410 ms |
29048 KB |
Output is correct |
46 |
Correct |
390 ms |
28904 KB |
Output is correct |
47 |
Correct |
349 ms |
27572 KB |
Output is correct |
48 |
Correct |
184 ms |
20060 KB |
Output is correct |
49 |
Correct |
314 ms |
28468 KB |
Output is correct |
50 |
Correct |
389 ms |
28640 KB |
Output is correct |
51 |
Correct |
405 ms |
29136 KB |
Output is correct |