이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#define mp make_pair
#define ll long long int
using namespace std;
ll N,M,S,T,U,V;
vector<vector<pair<ll,ll> > > adj;
vector<ll> distS;
vector<ll> distU;
vector<ll> distV;
void dijkstra(ll from, vector<ll> &dist) {
dist[from]=0;
vector<bool> vis(N+1);
priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > q;
q.push(mp(0,from));
while(!q.empty()) {
ll a=q.top().second;
q.pop();
if(vis[a]) continue;
vis[a]=true;
for(auto el : adj[a]) {
ll b=el.first, w=el.second;
if(dist[b]>dist[a]+w) {
dist[b]=dist[a]+w;
q.push(mp(dist[b],b));
}
}
}
}
ll res;
vector<bool> visth;
vector<ll> distth;
void calc(ll x) {
if(visth[x]) return;
// cout<<x<<"\n";
visth[x]=true;
distth[x]=distU[x];
for(auto el:adj[x]) {
ll b=el.first, w=el.second;
if(distS[b]==distS[x]-w) {
calc(b);
distth[x]=min(distth[x],distth[b]);
} else {
// calc(b);
// distth[x]=min(distth[x],distth[b]+w);
}
}
// cout<<x<<" "<<distth[x]+distV[x]<<"\n";
res=min(res,distth[x]+distV[x]);
}
void calc2(ll x) {
if(visth[x]) return;
// cout<<x<<"\n";
visth[x]=true;
distth[x]=distV[x];
for(auto el:adj[x]) {
ll b=el.first, w=el.second;
if(distS[b]==distS[x]-w) {
calc2(b);
distth[x]=min(distth[x],distth[b]);
} else {
// calc(b);
// distth[x]=min(distth[x],distth[b]+w);
}
}
// cout<<x<<" "<<distth[x]+distV[x]<<"\n";
res=min(res,distth[x]+distU[x]);
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin>>N>>M>>S>>T>>U>>V;
adj.resize(N+1);
for(ll i=0;i<M;i++) {
ll a,b,c;
cin>>a>>b>>c;
adj[a].push_back(mp(b,c));
adj[b].push_back(mp(a,c));
}
distS.assign(N+1,LLONG_MAX);
dijkstra(S,distS);
distU.assign(N+1,LLONG_MAX);
dijkstra(U,distU);
distV.assign(N+1,LLONG_MAX);
dijkstra(V,distV);
res=distU[V];
visth.resize(N+1);
distth.resize(N+1);
calc(T);
visth.clear();
distth.clear();
visth.resize(N+1);
distth.resize(N+1);
calc2(T);
cout<<res;
}
# | 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... |