제출 #66807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66807		quoriess	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	783 ms	19724 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);
	
	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);
	}
	cout << snc<<"\n";
	return 0;
}

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