Submission #67467

#	Time	Username	Problem	Language	Result	Execution time	Memory
67467		quoriess	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1321 ms	94668 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));
			}
		}
	}	
}
vector<vector<pii> > gdag(100006,vector<pii>());
vector<lli> in(100006,0);
/*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);
	}
	
}*/
/*
 
 * */
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";
	upminu[node]=min(upminu[node],distu[node]);
	upminv[node]=min(upminv[node],distv[node]);
	ans=min(ans,distv[node]+upminu[node]);
	ans=min(ans,distu[node]+upminv[node]);
	for (auto kms:dag[node])
	{
		in[kms.first]--;
		upminv[kms.first]=min(upminv[kms.first],upminv[node]);
		upminu[kms.first]=min(upminu[kms.first],upminu[node]);
		if(in[kms.first]<=0)dfs(kms.first,dag,upminv,upminu,distu,distv);
		//cout << node<<"->"<<kms.first<<"\n";
	}
}
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));
	}
	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>());
	for(int i=1;i<=n;i++){
		for (auto nodi:adj[i])
		{
			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));
				in[nodi.first]++;
			}
		}
	}
	dijk(u,distu,preu);
	
	dijk(v,distv,prev);
	vector<lli> upminv(n+1,1e15),upminu(n+1,1e15),upminvters(n+1,1e15),upminuters(n+1,1e15);
	upminv[s]=distv[s];
	upminu[s]=distu[s];
	upminu[s]=distu[s];
	upminv[s]=distv[s];
	ans=distv[u];
	if(in[s]!=0){
		//cout << "bozuk\n";
		return -1;
		
	}
	dfs(s,dag,upminv,upminu,distu,distv);
	cout<<ans<<"\n";
	return 0;
}

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