#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m,s,t,u,v,Ls[100005],Lu[100005],Lv[100005],length=1e9;
vector<int> trace[100005],path;
vector<pair<int,int>> adj[100005];
vector<vector<int>> op;
void dijkstra(int start, int* L){
for (int i=1; i<=n; i++) L[i]=1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
L[start]=0;
pq.push({0,start});
while (!pq.empty()){
auto [a,b]=pq.top();
pq.pop();
if (a>L[b]) continue;
for (auto [nx,w]:adj[b]){
if (a+w<L[nx]){
L[nx]=a+w;
trace[nx].clear();
trace[nx].push_back(b);
pq.push({L[nx],nx});
}
else if (a+w==L[nx]){
trace[nx].push_back(b);
}
}
}
}
void back(int a){
path.push_back(a);
if (a==s){
op.push_back(path);
path.pop_back();
return;
}
for (int i:trace[a]){
back(i);
}
path.pop_back();
}
main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> m >> s >> t >> u >> v;
for (int i=1; i<=m; i++){
int a,b,c; cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
dijkstra(s,Ls);
// cout << Ls[t] << "\n";
back(t);
dijkstra(u,Lu);
dijkstra(v,Lv);
for (auto a:op){
int k=1e9;
for (int i=a.size()-1; i>=0; i--){
k=min(k,Lv[a[i]]);
}
for (int i=a.size()-1; i>=0; i--){
length=min(length,Lu[a[i]]+k);
}
}
cout << length;
}
Compilation message (stderr)
commuter_pass.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |