제출 #869650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869650		PM1	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	1244 ms	51540 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long int
const ll mxn=1e5+5;
ll n,m,st,fn,uu,vv,park[mxn],mark[mxn];
ll dis[mxn][4];
vector<ll>par[mxn],v[mxn];
set<pair<ll,pair<ll,ll> > >s;
struct yall{
	ll x,y,w;
};
yall yal[mxn*4];
void up(ll id,ll type,ll d,ll 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){
	}
	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(ll root){
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<4;j++){
			dis[i][j]=(i==root && j==0)?0:1e18;
			s.insert({dis[i][j],{i,j} });
		}
	}
	while(s.size()){
		auto x=*s.begin();
		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(ll z){
	park[z]=1;
	for(auto i:par[z]){
		if(mark[i]){
			continue;
		}
		ll 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);
	}
}
main(){
	cin>>n>>m;
	cin>>st>>fn>>uu>>vv;
	for(ll 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(ll i=0;i<4;i++){
		ans=min(ans,dis[vv][i]);
	}
	cout<<ans<<endl;

}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main(){
      | ^~~~

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