이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define N 1000000
#define inf ll(1e18+7)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef double db;
const int M = 1e9+7;
int n,m,s,t,x,y;
vector<pll> adj1[N+3],adj2[N+3];
vector<int> tmp[N+3];
ll d[N+3];
void dijkstra1(){
priority_queue<pll,vector<pll>,greater<pll>> qQ;
fill(d+1,d+n+1,inf);
d[s]=0;
qQ.push({0,s});
while(!qQ.empty()){
ll du=qQ.top().fi;
int u=qQ.top().se;
qQ.pop();
if(du!=d[u]) continue;
for(auto P:adj1[u]){
ll w=P.fi;
int v=P.se;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
tmp[v].clear();
tmp[v].pb(u);
qQ.push({d[v],v});
}
else if(d[v]==d[u]+w)
tmp[v].pb(u);
}
}
}
void dijkstra2(){
priority_queue<pll,vector<pll>,greater<pll>> qQ;
fill(d+1,d+n+1,inf);
d[x]=0;
qQ.push({0,x});
while(!qQ.empty()){
ll du=qQ.top().fi;
int u=qQ.top().se;
qQ.pop();
if(du!=d[u]) continue;
for(auto P:adj2[u]){
ll w=P.fi;
int v=P.se;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
qQ.push({d[v],v});
}
}
for(auto P:adj1[u]){
ll w=P.fi;
int v=P.se;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
qQ.push({d[v],v});
}
}
}
}
void DFS(int u, int p){
for(auto v:tmp[u]) if(v!=p){
adj2[u].pb({0,v});
adj2[v].pb({0,u});
DFS(v,u);
}
}
void Solve(){
dijkstra1();
DFS(t,0);
dijkstra2();
cout << d[y];
}
void Inp(){
cin >> n >> m >> s >> t >> x >> y;
for(int u,v,w,i=1; i<=m; i++){
cin >> u >> v >> w;
adj1[u].pb({w,v});
adj1[v].pb({w,u});
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;
// cin >> T;
while(T--){
Inp();
Solve();
}
}
# | 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... |