Submission #158867

#	Time	Username	Problem	Language	Result	Execution time	Memory
158867		GioChkhaidze	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	873 ms	29416 KiB

commuter_pass

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N=2e5+5;

int n,m,S,T,U,V;
long long D[N][6],dp[N],fix[N];
vector < pair < long long  , int > > v[N];

void Dijkstra(int type) {
	multiset < pair < long long , int > > st;
	for (int i=1; i<=n; i++) 
		fix[i]=0,D[i][type]=1e17;
	
	if (!type) D[V][0]=0,st.insert({D[V][0],V});
		else 
	if (type==1) D[U][1]=0,st.insert({D[U][1],U});
		else
	if (type==2) D[S][2]=0,st.insert({D[S][2],S});
		else
	if (type==3) D[T][3]=0,st.insert({D[T][3],T});
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;
		for (int i=0; i<v[x].size(); i++){
			long long to=v[x][i].F,dist=v[x][i].S;
			if (!fix[to] && D[x][type]+dist<D[to][type]) {
				D[to][type]=D[x][type]+dist;
				st.insert({D[to][type],to});
			}
		}
	}
}

void FillDp(int type) {
	multiset < pair < long long , int > > st;
	long long d[N];

	for (int i=1; i<=n; i++) 
		fix[i]=0,d[i]=1e17;
		
	if (!type) {
		d[T]=0,dp[T]=min(dp[T],D[T][0]);
		st.insert({d[T],T});
	}
		else {
		d[S]=0,dp[S]=min(dp[S],D[S][0]);
		st.insert({d[S],S});	
	}
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;
		
		for (int i=0; i<v[x].size(); i++) {
			long long to=v[x][i].F,dist=v[x][i].S;
			if (D[to][2]+D[to][3]!=D[S][3]) continue;
			if (!fix[to] && d[x]+dist<=d[to]) {
				dp[to]=min(dp[to],min(dp[x],D[to][0]));
				d[to]=d[x]+dist;
				st.insert({d[to],to});
			}
		}
	}
}

main () {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	cin>>S>>T;
	cin>>U>>V;
	
	for (int i=1; i<=m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	
	Dijkstra(0);
	Dijkstra(1);
	Dijkstra(2);
	Dijkstra(3);
	
	long long ANS=D[V][1];
	
	for (int i=1; i<=n; i++) dp[i]=1e17;
		
	FillDp(0);
	
	for (int x=1; x<=n; x++) 
		if (D[x][2]+D[x][3]==D[S][3]) ANS=min(ANS,dp[x]+D[x][1]);
	
	for (int i=1; i<=n; i++) dp[i]=1e17;
	
	FillDp(1);
	
	for (int x=1; x<=n; x++) 
		if (D[x][2]+D[x][3]==D[S][3]) ANS=min(ANS,dp[x]+D[x][1]);
		

	cout<<ANS<<endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijkstra(int)':
commuter_pass.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++){
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void FillDp(int)':
commuter_pass.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:76:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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