이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define x first
#define y second
const int INF=1e18;
int n,m;
vector<vector<pair<int,int>>> adj;
vector<vector<int>> dp;
vector<vector<int>> dis1;
vector<bool> vis;
int ans=0;
void dijkstra(int s){
vector<int> dis(n,INF);
dis[s]=0;
priority_queue<pair<int,int>> pq;
pq.push({0,s});
while(pq.size()){
int a,b;tie(a,b)=pq.top();
pq.pop();
a=-a;
if(dis[b]!=a){
continue;
}
for(auto p:adj[b]){
if(dis[p.x]>dis[b]+p.y){
dis[p.x]=dis[b]+p.y;
pq.push({-dis[p.x],p.x});
}
}
}
dis1.push_back(dis);
}
void dfs(int k){
vis[k]=1;
for(auto p:adj[k]){
if(dis1[2][k]-dis1[2][p.x]==p.y){
if(!vis[p.x]){
dfs(p.x);
}
dp[0][k]=min(dp[0][k],dp[0][p.x]);
dp[1][k]=min(dp[1][k],dp[1][p.x]);
}
}
ans=min({ans,dp[1][k]+dis1[0][k],dis1[1][k]+dp[0][k]});
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int s,t,u,v;
cin>>n>>m>>s>>t>>u>>v;
s--;t--;u--;v--;
adj.resize(n);
for(int i=0;i<m;i++){
int a,b,c;cin>>a>>b>>c;a--;b--;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
dijkstra(u);
dijkstra(v);
dijkstra(s);
ans=dis1[0][v];
dp.resize(2);
dp[0]=dis1[0];
dp[1]=dis1[1];
vis.resize(n);
dfs(t);
cout<<ans<<endl;
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... |