이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t,u,v;
vector<vector<pair<int,int>>> adj;
vector<int> distU, distV, dpForward, dpBackward, distS, distT, dS, dT;
void dijkstra1(int node, vector<int>& dist){
priority_queue<pair<int,int>> pq;
pq.push({0,node});
while(!pq.empty()){
int x=pq.top().second; int d = -pq.top().first; pq.pop();
if (dist[x] != -1) continue;
dist[x] = d;
for (auto [y,w]: adj[x]){
int tmp=w+d;
pq.push({-tmp, y});
}
}
}
signed main(){
cin>>n>>m>>s>>t>>u>>v;
adj.resize(n+1);
for (int i=0; i<m; i++){
int x,y,w; cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
distU.resize(n+1,-1), distV.resize(n+1, -1), distS.resize(n+1,-1), distT.resize(n+1,-1), dpForward.resize(n+1,-1), dpBackward.resize(n+1,-1);
dS.resize(n+1,-1), dT.resize(n+1,-1);
dijkstra1(u, distU);
dijkstra1(v, distV);
dijkstra1(s, dS);
dijkstra1(t, dT);
vector<bool> vF(n+1,false), vB(n+1,false);
//now compute dpForward and dpBackward
priority_queue<pair<int,int>> pq;
pq.push({0,s});
dpForward[s] = distV[s];
while(!pq.empty()){
auto [d, node] = pq.top();
pq.pop();
d*=-1;
if (vF[node]) continue;
vF[node]=true;
for (auto [x,w]: adj[node]){
int tmp=d+w;
if (dT[x] != dT[node]-w) continue;
if (distS[x]==-1){
dpForward[x] = min(dpForward[node], distV[x]);
distS[x] = tmp;
} else if (distS[x] == tmp){
dpForward[x] = min(dpForward[x], min(dpForward[node],distV[x]));
} else if (tmp < distS[x]){
dpForward[x] = min(dpForward[node], distV[x]);
distS[x] = tmp;
}
pq.push({-tmp,x});
}
}
pq.push({0,t});
dpBackward[t] = distV[t];
while(!pq.empty()){
auto [d, node] = pq.top();
pq.pop();
d*=-1;
if (vB[node]) continue;
//cout<<node<<'\n';
vB[node]=true;
for (auto [x,w]: adj[node]){
if (dS[x] != dS[node]-w) continue;
int tmp=d+w;
if (distT[x]==-1){
dpBackward[x] = min(dpBackward[node], distV[x]);
distT[x] = tmp;
} else if (distT[x] == tmp){
dpBackward[x] = min(dpBackward[x], min(dpBackward[node],distV[x]));
} else if (tmp < distT[x]){
dpBackward[x] = min(dpBackward[node], distV[x]);
distT[x] = tmp;
}
pq.push({-tmp,x});
}
}
//cout<<'\n';
int ans=distU[v];
for (int i=1; i<=n; i++){
if (vF[i]==false or vB[i]==false) continue;
//cout<<i<<' '<<dpForward[i]<<' '<<dpBackward[i]<<'\n';
ans=min(ans, distU[i]+min(dpBackward[i],dpForward[i]));
}
cout<<ans<<'\n';
}
# | 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... |