Submission #869654

#	Time	Username	Problem	Language	Result	Execution time	Memory
869654		PM1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1448 ms	58496 KiB

commuter_pass

#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;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45