이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long int
const int mxn=2e5+5;
int n,m,st,fn,uu,vv,park[mxn],mark[mxn];
ll dis[mxn][4];
vector<int>par[mxn],v[mxn];
set<pair<ll,pair<int,int> > >s;
struct yall{
ll x,y,w;
};
yall yal[mxn*2];
void up(int id,int type,ll d,int xx){
ll z=yal[id].x^yal[id].y^xx,ww=(type==1 || type==2)?0:yal[id].w;
if(dis[z][type]<d+ww){
return;
}
else if(dis[z][type]==d+ww){
par[z].push_back(id);
}
else{
par[z].clear();
par[z].push_back(id);
s.erase({dis[z][type],{z,type}});
dis[z][type]=d+ww;
s.insert({dis[z][type],{z,type}});
}
}
void dij(int root){
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
dis[i][j]=(i==root && j==0)?0:1e15;
s.insert({dis[i][j],{i,j} });
}
}
while(s.size()){
auto x=*s.begin();
assert(x.fr>-1);
s.erase({x.fr,{x.sc.fr,x.sc.sc}});
for(auto i:v[x.sc.fr]){
if(x.sc.sc==0){
up(i,0,x.fr,x.sc.fr);
}
if(x.sc.sc==0 || x.sc.sc==1){
if(x.sc.fr==yal[i].x && mark[i]==1){
up(i,1,x.fr,x.sc.fr);
}
if(x.sc.fr==yal[i].y && mark[i]==2){
up(i,1,x.fr,x.sc.fr);
}
}
if(x.sc.sc==0 || x.sc.sc==2){
if(x.sc.fr==yal[i].x && mark[i]==2){
up(i,2,x.fr,x.sc.fr);
}
if(x.sc.fr==yal[i].y && mark[i]==1){
up(i,2,x.fr,x.sc.fr);
}
}
if(x.sc.sc!=0){
up(i,3,x.fr,x.sc.fr);
}
}
}
}
void dfs(int z){
park[z]=1;
for(auto i:par[z]){
if(mark[i]){
continue;
}
int a=yal[i].x^yal[i].y^z;
if(a==yal[i].x){
mark[i]=1;
}
else{
mark[i]=2;
}
if(park[a]){
continue;
}
dfs(a);
}
}
int main(){
cin>>n>>m;
cin>>st>>fn>>uu>>vv;
for(int i=1;i<=m;i++){
cin>>yal[i].x>>yal[i].y>>yal[i].w;
v[yal[i].x].push_back(i);
v[yal[i].y].push_back(i);
}
dij(st);
dfs(fn);
dij(uu);
ll ans=1e18;
for(int i=0;i<4;i++){
ans=min(ans,dis[vv][i]);
}
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... |