Submission #869359

#	Time	Username	Problem	Language	Result	Execution time	Memory
869359		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	711 ms	48048 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long int
const int mxn=1e5+5;
ll n,m,dis[mxn],s,t,u,v,ans=1e18,mark[mxn];
vector<int>par[mxn];
set<pair<ll,ll> >st,yal[mxn];
void dfs(int z){
	mark[z]=1;
	dis[z]=0;
	for(auto i:par[z]){
		if(!mark[i]){
			dfs(i);
		}
	}
}
void dij(){
	while(st.size()){
		auto x=*st.begin();
		st.erase({x.fr,x.sc});
		for(auto i:yal[x.sc]){
			if(dis[i.fr]>x.fr+i.sc){
				st.erase({dis[i.fr],i.fr});
				dis[i.fr]=x.fr+i.sc;
				st.insert({dis[i.fr],i.fr});
				par[i.fr].clear();
				par[i.fr].push_back(x.sc);
			}
			else if(dis[i.fr]==x.fr+i.sc){
				par[i.fr].push_back(x.sc);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	cin>>s>>t>>u>>v;
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		yal[x].insert({y,w});
		yal[y].insert({x,w});
	}
	for(int i=1;i<=n;i++){
		dis[i]=(i==s)?0:1e18;
		st.insert({dis[i],i});
	}
	dij();
	for(int i=1;i<=n;i++){
		dis[i]=1e18;
	}
	dfs(t);
	for(int i=1;i<=n;i++){
		st.insert({dis[i],i});
	}
	dij();
	cout<<dis[v];
}

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