이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e9,LINF=1e18,MAXN=1e5+1;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"="; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
int N,M,S,T,U,V;
vector<pair<int,ll>> adj[MAXN];
vector<int> dag[MAXN];
vector<ll> dist1(MAXN),dist2(MAXN),dpU(MAXN,LINF),dpV(MAXN,LINF),dp(MAXN,LINF);
vector<bool> visited(MAXN);
vector<int> topo;
void Dijkstra(int src,vector<ll>& dist){
for(int i=1;i<=N;i++){
dist[i]=0;
visited[i]=0;
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
pq.push({0,src});
while(!pq.empty()){
pair<ll,int> vrh=pq.top(); pq.pop();
if(!visited[vrh.se]){
visited[vrh.se]=true;
dist[vrh.se]=vrh.fi;
for(auto x:adj[vrh.se]){
if(!visited[x.fi]) pq.push({dist[vrh.se]+x.se,x.fi});
}
}
}
}
void TopoSort(int node){
visited[node]=true;
for(auto x:dag[node]) if(!visited[x]) TopoSort(x);
topo.pb(node);
}
void Solve(){
cin>>N>>M>>S>>T>>U>>V;
for(int i=0;i<M;i++){
int u,v,w;
cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
Dijkstra(S,dist1);
Dijkstra(T,dist2);
for(int i=1;i<=N;i++){
for(auto x:adj[i]){
if(dist1[i]+x.se+dist2[x.fi]==dist1[T]){
dag[i].pb(x.fi);
//PRINT(i); PRINT(x.fi);
}
}
}
for(int i=1;i<=N;i++) visited[i]=false;
TopoSort(S); reverse(all(topo));
//PRINTvec(topo);
Dijkstra(U,dist1);
Dijkstra(V,dist2);
while(!topo.empty()){
int node=topo.back(); topo.pop_back();
//PRINT(node); PRINT(dist1[node]); PRINT(dist2[node]);
dp[node]=dist1[node]+dist2[node]; //PRINT(dp[node]);
dpU[node]=dist1[node]; //PRINT(dpU[node]);
dpV[node]=dist2[node]; //PRINT(dpV[node]);
for(auto x:dag[node]){
dpU[node]=min(dpU[node],dpU[x]);
dpV[node]=min(dpV[node],dpV[x]);
dp[node]=min(dp[node],dp[x]);
}
dp[node]=min({dp[node],dpU[node]+dist2[node],dpV[node]+dist1[node]});
//PRINT(dp[node]); PRINT(dpU[node]); PRINT(dpV[node]);
}
cout<<min(dp[S],dist1[V])<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
//cin>>t;
t=1;
while(t--){
Solve();
}
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... |