Submission #219898

#	Time	Username	Problem	Language	Result	Execution time	Memory
219898		sensiel	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	1521 ms	262148 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX_NODE = 100005;
const int INFINI = 2000000000;

typedef struct node
{
	int iNode;
	int prix;
}node;

typedef struct event
{
	int tps;
	int iNode;
	int parent;
	bool operator< (const event & other)const
	{
		return tps > other.tps;
	}
}event;

int nNode;
int nArc;
int S,T;
int U,V;

vector<node> adj[MAX_NODE];
int minDisU[MAX_NODE];
int minDisV[MAX_NODE];
int tpsmin[MAX_NODE];

int dp[MAX_NODE][2][2];

void init()
{
	cin >> nNode >> nArc;
	cin >> S >> T;
	cin >> U >> V;

	

	for(int iArc = 0; iArc < nArc; iArc++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}

	for(int iNode = 0; iNode <= nNode; iNode++)
	{
		minDisU[iNode] = INFINI;
		minDisV[iNode] = INFINI;
		tpsmin[iNode] = INFINI;
		dp[iNode][false][false] = 0;
		dp[iNode][true][false] = INFINI;
		dp[iNode][true][true] = INFINI;
		dp[iNode][false][true] = INFINI;
	}
	dp[0][false][false] = INFINI;
}

signed main()
{
    init();
	priority_queue<event> dU;
	dU.push({0,U,-1});
	while(!dU.empty())
	{
		event actual = dU.top();
		dU.pop();
		if(actual.tps <= minDisU[actual.iNode])
		{
			minDisU[actual.iNode] = actual.tps;
			int nVoisin = adj[actual.iNode].size();
			for(int iVoisin = 0; iVoisin < nVoisin; iVoisin++)
			{
			    
				node voisin = adj[actual.iNode][iVoisin];
				if(minDisU[voisin.iNode] >= actual.tps + voisin.prix)
				{
				    
					minDisU[voisin.iNode] = actual.tps + voisin.prix;
					dU.push({minDisU[voisin.iNode], voisin.iNode, actual.iNode});
				}
			}
		}
	}

	priority_queue<event> dV;
	dV.push({0,V,-1});
	while(!dV.empty())
	{
		event actual = dV.top();
		dV.pop();
		if(actual.tps <= minDisV[actual.iNode])
		{
			minDisV[actual.iNode] = actual.tps;
			int nVoisin = adj[actual.iNode].size();
			for(int iVoisin = 0; iVoisin < nVoisin; iVoisin++)
			{
				node voisin = adj[actual.iNode][iVoisin];
				if(minDisV[voisin.iNode] >= actual.tps + voisin.prix)
				{
					minDisV[voisin.iNode] = actual.tps + voisin.prix;
					dV.push({minDisV[voisin.iNode], voisin.iNode, actual.iNode});
				}
			}
		}
	}

	priority_queue<event> pq;
	pq.push({0,S,0});
	while(!pq.empty())
	{
		event actual = pq.top();
		pq.pop();
		if(actual.tps <= tpsmin[actual.iNode])
		{
			tpsmin[actual.iNode] = actual.tps;
			dp[actual.iNode][false][true] = min(dp[actual.iNode][false][true],
			                                min(dp[actual.parent][false][true],  
			                                    minDisU[actual.iNode]));
			dp[actual.iNode][true][false] = min(dp[actual.iNode][true][false],
			                                min(dp[actual.parent][true][false], 
			                                    minDisV[actual.iNode]));
			dp[actual.iNode][true][true] = min(dp[actual.iNode][true][true],
			                               min( dp[actual.parent][true][true], 
			                               min(minDisV[actual.iNode] + minDisU[actual.iNode], 
			                               min(dp[actual.iNode][true][false] + minDisU[actual.iNode], 
			                               dp[actual.iNode][false][true] + minDisV[actual.iNode]))));
			int nVoisin = adj[actual.iNode].size();
			for(int iVoisin = 0; iVoisin < nVoisin; iVoisin++)
			{
				node voisin = adj[actual.iNode][iVoisin];
				if(tpsmin[voisin.iNode] >= actual.tps + voisin.prix)
				{
					tpsmin[voisin.iNode] = actual.tps + voisin.prix;

					pq.push({tpsmin[voisin.iNode], voisin.iNode, actual.iNode});
				}
			}
		}
	}
	cout << min(minDisU[V], dp[T][true][true]);
}

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