이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
const Lli MAX=1e18;
vector<pair<I,I>>adjs[N];
vector<I>incs[N];
Lli diss[N];
priority_queue<pair<Lli,I>>ques;
void add1(I a,Lli d,I p){
if(d>diss[a])return;
if(d<diss[a])diss[a]=d,incs[a].clear();
if(d==diss[a])incs[a].push_back(p);
ques.push({-d,a});
}
void add2(I a,Lli d){
if(d>=diss[a])return;
ques.push({-(diss[a]=d),a});
}
void dfs(I a){
for(auto b:incs[a]){
adjs[b].push_back({a,0});
dfs(b);
}
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I n,m;cin>>n>>m;
I s,t;cin>>s>>t,s--,t--;
I u,v;cin>>u>>v,u--,v--;
for(I i=0;i<m;i++){
I a,b,c;cin>>a>>b>>c,a--,b--;
adjs[a].push_back({b,c});
adjs[b].push_back({a,c});
}
fill_n(diss,n,MAX),add2(s,0);
while(ques.size()){
auto[d,a]=ques.top();ques.pop();
if((d=-d)!=diss[a])continue;
for(auto[b,c]:adjs[a])add1(b,d+c,a);
}
dfs(t);
Lli res=MAX;
fill_n(diss,n,MAX),add2(u,0);
while(ques.size()){
auto[d,a]=ques.top();ques.pop();
if((d=-d)!=diss[a])continue;
for(auto[b,c]:adjs[a])add2(b,d+c);
}
res=min(res,diss[v]);
fill_n(diss,n,MAX),add2(v,0);
while(ques.size()){
auto[d,a]=ques.top();ques.pop();
if((d=-d)!=diss[a])continue;
for(auto[b,c]:adjs[a])add2(b,d+c);
}
res=min(res,diss[u]);
printf("%lli\n",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... |