Submission #219902

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

commuter_pass

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

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

typedef struct node
{
	int iNode;
	long long 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];
long long minDisU[MAX_NODE];
long long minDisV[MAX_NODE];
long long tpsmin[MAX_NODE];

long long 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]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:86:35: warning: narrowing conversion of 'minDisU[voisin.node::iNode]' from 'long long int' to 'int' inside { } [-Wnarrowing]
      dU.push({minDisU[voisin.iNode], voisin.iNode, actual.iNode});
               ~~~~~~~~~~~~~~~~~~~~^
commuter_pass.cpp:108:35: warning: narrowing conversion of 'minDisV[voisin.node::iNode]' from 'long long int' to 'int' inside { } [-Wnarrowing]
      dV.push({minDisV[voisin.iNode], voisin.iNode, actual.iNode});
               ~~~~~~~~~~~~~~~~~~~~^
commuter_pass.cpp:142:34: warning: narrowing conversion of 'tpsmin[voisin.node::iNode]' from 'long long int' to 'int' inside { } [-Wnarrowing]
      pq.push({tpsmin[voisin.iNode], voisin.iNode, actual.iNode});
               ~~~~~~~~~~~~~~~~~~~^

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