Submission #66811

#	Time	Username	Problem	Language	Result	Execution time	Memory
66811		quoriess	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	991 ms	21392 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));
			}
		}
	}
	
}
/*
5 7
1 3
1 5
1 2 1
2 3 3
1 3 2
3 4 1
3 5 2
1 4 1
1 5 7 
 * */
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> distS(n+1),preS(n+1);
	dijk(s,distS,preS);
	
	/*
	 * 
	 st 1 bozuk
	 vector<lli> distv(n+1),prev(n+1);
	
	dijk(v,distv,prev);
	lli snc=1e17;
	for (int i = t; i != -1 ; i=preS[i])
	{
		//cout <<"i: "<<i<<"\n";
		snc=min(distv[i],snc);
	}
	*/
	//st 2
	 vector<lli> distv(n+1),prev(n+1);
	
	dijk(v,distv,prev);
	
	 vector<lli> distu(n+1),preu(n+1);
	dijk(u,distu,preu);
	lli snc=distu[v];
	for (int i = t; i != -1 ; i=preS[i])
	{
		snc=min(distv[i]+distu[i],snc);
	}
	cout << snc<<"\n";
	return 0;
}

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