Submission #66986

#	Time	Username	Problem	Language	Result	Execution time	Memory
66986		quoriess	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	1525 ms	61436 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<vector<pii> > adj;
void dijk(int start,vector<lli>& dist,vector<lli>& pre){
	set<pii> nodes;
	int len=dist.size();
	dist=vector<lli>(len,1e17);
	nodes.insert(pii(0,start));
	dist[start]=0;
	pre=vector<lli>(len,-1);
	while(!nodes.empty())
	{
		auto sim=*nodes.begin();		
		nodes.erase(sim);
		for(auto u:adj[sim.second]){
			if(dist[sim.second]+u.second<dist[u.first]){
				if(nodes.find(pii(dist[u.first],u.first))!=nodes.end())
					nodes.erase(pii(dist[u.first],u.first));
				dist[u.first]=dist[sim.second]+u.second;
				pre[u.first]=sim.second;
				nodes.insert(pii(dist[u.first],u.first));
			}
		}
	}	
}
bool marked2[100006];
vector<vector<pii> > gdag(100006,vector<pii>());
void eliminate(int node,vector<vector<pii> >& dag){
	marked2[node]=true;
	for (auto u:dag[node])
	{
		gdag[u.first].push_back(pii(node,u.second));
		//cout << "gdag'a ekledi: "<<u.first <<"->"<<node<<"\n";
		if(!marked2[u.first])eliminate(u.first,dag);
	}
	
}
/*
 
 * */
 bool marked3[100006];
typedef pair<lli,pii> data;
lli ans=1e17;
void dfs(int node,vector<vector<pii> >& dag,vector<lli>& upminv,vector<lli>& upminu,vector<lli>& distu,vector<lli>& distv){
	//cout << "sh dag: "<<node<<"\n";
	//cout << "upminu: "<<upminu[node]<<" upminv: "<<upminv[node]<<"\n";
	marked3[node]=true;
	ans=min(ans,distv[node]+upminu[node]);
	ans=min(ans,distu[node]+upminv[node]);
	for (auto u:dag[node])
	{
		
		//cout << node<<"->"<<u.first<<"\n";
		if(!marked3[u.first])dfs(u.first,dag,upminv,upminu,distu,distv);
	}
}

int main(){
	int n,m;
	cin>>n>>m;
	lli s,t,u,v;
	cin>>s>>t>>u>>v;
	adj=vector<vector<pii> >(n+1,vector<pii>());
	for (int i = 0; i < m; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		adj[a].push_back(pii(b,c));
		adj[b].push_back(pii(a,c));
	}
	/*
s'den shortest path bul 
	 * */
	vector<lli> distu(n+1),distv(n+1),preu(n+1),prev(n+1), dists(n+1),pres(n+1),distt(n+1),pret(n+1);
	dijk(s,dists,pres);
	dijk(t,distt,pret);
	vector<vector<pii> > dag(n+1,vector<pii>()),dagters(n+1,vector<pii>());
	//bool mark4[100006];
	for(int i=1;i<=n;i++){
		for (auto nodi:adj[i])
		{
			//if(mark4[nodi.first]==true)continue;
			if(nodi.second+dists[i]+distt[nodi.first]==dists[t]){
				dag[i].push_back(pii(nodi.first,nodi.second));
				dagters[nodi.first].push_back(pii(i,nodi.second));
			}
		}
	}
	dijk(u,distu,preu);
	
	dijk(v,distv,prev);
	//eliminate(t,dagters);
	vector<lli> upminv(n+1,1e15),upminu(n+1,1e15);
	upminv[s]=distv[s];
	upminu[s]=distu[s];
	queue<int> nodes;
	nodes.push(s);
	bool mark[100006];
	while(!nodes.empty()){
		int ust=nodes.front();
		nodes.pop();
		mark[ust]=true;
		for(auto a: dag[ust]){
			upminv[a.first]=min(upminv[a.first],min(distv[a.first],upminv[ust]));
			upminu[a.first]=min(upminu[a.first],min(distu[a.first],upminu[ust]));
			if(!mark[a.first])nodes.push(a.first);
		}
	}
	ans=distv[u];
	dfs(s,dag,upminv,upminu,distu,distv);
	cout<<ans<<"\n";
	return 0;
}

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