oj.uz

Submission #219898

# Submission time Handle Problem Language Result Execution time Memory
219898 2020-04-06T16:33:26 Z sensiel Commuter Pass (JOI18_commuter_pass) C++11
0 / 100
 1521 ms 262148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 27872 KB Output is correct
2 Runtime error 1521 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 24804 KB Output is correct
2 Correct 495 ms 24424 KB Output is correct
3 Correct 500 ms 24420 KB Output is correct
4 Correct 498 ms 24552 KB Output is correct
5 Correct 494 ms 24548 KB Output is correct
6 Correct 497 ms 23952 KB Output is correct
7 Correct 513 ms 27108 KB Output is correct
8 Correct 497 ms 26984 KB Output is correct
9 Correct 505 ms 26972 KB Output is correct
10 Correct 493 ms 26852 KB Output is correct
11 Incorrect 177 ms 15484 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 628 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 27872 KB Output is correct
2 Runtime error 1521 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -