이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e18;
int n,m,S,T,U,V;
vector<array<int,2>> v[N];
vector<int> dist_S,dist_T,dist_U,dist_V;
vector<int> dijkstra(int st){
vector<int> dist(N,INF);
dist[st]=0;
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
pq.push({0,st});
while(!pq.empty()){
int d=pq.top()[0],c=pq.top()[1];
pq.pop();
if(d>dist[c]) continue;
for(array<int,2> x:v[c]){
if(d+x[1]<dist[x[0]]){
dist[x[0]]=d+x[1];
pq.push({d+x[1],x[0]});
}
}
}
return dist;
}
int Update(){
int res=INF;
vector<int> dist(N,INF),ans(N,INF);
dist[S]=0;
ans[S]=dist_V[S];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
pq.push({0,S});
while(!pq.empty()){
int d=pq.top()[0],c=pq.top()[1];
pq.pop();
if(d>dist[c]) continue;
ans[c]=min(ans[c],dist_V[c]);
if(dist[c]+dist_T[c]==dist_S[T]) res=min(res,dist_U[c]+ans[c]);
for(array<int,2> x:v[c]){
if(d+x[1]<dist[x[0]]){
dist[x[0]]=d+x[1];
ans[x[0]]=ans[c];
pq.push({d+x[1],x[0]});
}
if(d+x[1]==dist[x[0]]) ans[x[0]]=min(ans[x[0]],ans[c]);
}
}
return res;
}
int Update2(){
int res=INF;
vector<int> dist(N,INF),ans(N,INF);
dist[S]=0;
ans[S]=dist_U[S];
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> pq;
pq.push({0,S});
while(!pq.empty()){
int d=pq.top()[0],c=pq.top()[1];
pq.pop();
if(d>dist[c]) continue;
ans[c]=min(ans[c],dist_U[c]);
if(dist[c]+dist_T[c]==dist_S[T]) res=min(res,dist_V[c]+ans[c]);
for(array<int,2> x:v[c]){
if(d+x[1]<dist[x[0]]){
dist[x[0]]=d+x[1];
ans[x[0]]=ans[c];
pq.push({d+x[1],x[0]});
}
if(d+x[1]==dist[x[0]]) ans[x[0]]=min(ans[x[0]],ans[c]);
}
}
return res;
}
void _(){
cin >> n >> m >> S >> T >> U >> V;
for(int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
dist_S=dijkstra(S),dist_T=dijkstra(T),dist_U=dijkstra(U),dist_V=dijkstra(V);
int Ans=dist_U[V];
Ans=min(Ans,Update());
Ans=min(Ans,Update2());
cout << Ans << '\n';
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# | 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... |