Submission #868454

#	Time	Username	Problem	Language	Result	Execution time	Memory
868454		amirhoseinfar1385	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	955 ms	55520 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,maxm=200000+10;
struct yal{
	long long u,v,w,te,dov;
	long long getad(long long fu){
		long long ret=(u^v^fu);
		return ret;
	}
};
yal alled[maxm];
vector<long long>adj[maxn];
long long dis[maxn];
long long inf=1e15;
long long n,m,s,t,fu,fv,vis[maxn];

void firstdij(){
	set<pair<long long,pair<long long,long long>>>st;
	for(auto x:adj[s]){
		st.insert(make_pair(alled[x].w,make_pair(alled[x].getad(s),x)));	
	}
	dis[s]=0;
	while((long long)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
		if(x.first>dis[x.second.first]){
			continue;
		}
		alled[x.second.second].dov=1;
		dis[x.second.first]=x.first;
		if(alled[x.second.second].u==x.second.first){
			swap(alled[x.second.second].u,alled[x.second.second].v);
		}
		for(auto y:adj[x.second.first]){
			st.insert(make_pair(alled[y].w+x.first,make_pair(alled[y].getad(x.second.first),y)));
		}
	}
}

void dfs(long long u){
	if(vis[u]==1){
		return ;
	}
	vis[u]=1;
	for(auto x:adj[u]){
		if(alled[x].v==u&&alled[x].dov==1){
			alled[x].te=1;
			dfs(alled[x].u);
		}
	}
}
long long visd[maxn][5];

long long dij(){
	set<pair<long long ,pair<long long,long long>>>st;
	st.insert(make_pair(0,make_pair(fu,0)));
	while((long long)st.size()>0){
		auto x=*st.begin();
		st.erase(x);
	//	cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<"\n";
		if(visd[x.second.first][x.second.second]==1){
			continue;
		}
		visd[x.second.first][x.second.second]=1;
		if(x.second.first==fv){
			return x.first;
		}
		for(auto y:adj[x.second.first]){
			if(alled[y].te){
				if(x.second.second==0){
					if(alled[y].u==x.second.first){
						st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
					}
					else{
						st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
					}
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0)));
				}
				if(x.second.second==1){
					if(alled[y].u==x.second.first){
						st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
					}
					else{
					//	st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
					}
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
				}
				if(x.second.second==2){
					if(alled[y].u==x.second.first){
					//	st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
					}
					else{
						st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
					}
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
				}
				if(x.second.second==3){
					if(alled[y].u==x.second.first){
					//	st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),1)));
					}
					else{
					//	st.insert(make_pair(x.first,make_pair(alled[y].getad(x.second.first),2)));
					}
						st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
				}
			}
			else{
				if(x.second.second==0){
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),0)));
				}
				if(x.second.second==1){
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));

				}
				if(x.second.second==2){
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));

				}
				if(x.second.second==3){
					st.insert(make_pair(x.first+alled[y].w,make_pair(alled[y].getad(x.second.first),3)));
				}
			}
		}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(long long i=0;i<maxn;i++){
		dis[i]=inf;
	}
	cin>>n>>m;
	cin>>s>>t;
	cin>>fu>>fv;
	for(long long i=0;i<m;i++){
		cin>>alled[i].u>>alled[i].v>>alled[i].w;	
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);
	}
	firstdij();
	//cout<<"salam"<<endl;
	dfs(t);
	cout<<dij()<<"\n";
}

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