Submission #41210

#	Time	Username	Problem	Language	Result	Execution time	Memory
41210		MatheusLealV	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	719 ms	24484 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define N 100005
#define inf 2000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, m, S, T, U, V, visited[N];

ll dist[N][5], from_u[N][5], ans = inf;

vector<pii> grafo[N];

void dijkstra(int x, int f, int flag)
{
	priority_queue<pii, vector<pii>, greater<pii> > pq;

	for(int i = 1; i <= n; i++) dist[i][f] = inf;

	dist[x][f] = 0, pq.push(pii(0, x));

	while(!pq.empty())
	{
		int x = pq.top().s, d = pq.top().f;

		pq.pop();

		for(auto v: grafo[x])
		{
			if(dist[v.f][f] > dist[x][f] + v.s)
			{
				dist[v.f][f] = dist[x][f] + v.s;

				if(flag == 1) from_u[v.f][0] = min(from_u[x][0], dist[v.f][0]);

				else if(flag == 2) from_u[v.f][1] = min(from_u[x][1], dist[v.f][0]);

				pq.push(pii(dist[v.f][f], v.f));
			}
			else if(dist[v.f][f] == dist[x][f] + v.s)
			{
				if(flag == 1) from_u[v.f][0] = min(from_u[v.f][0], min(from_u[x][0], dist[v.f][0]));

				else if(flag == 2) from_u[v.f][1] = min(from_u[v.f][1], min(from_u[x][1], dist[v.f][0]));
			}
		}
	}
}

ll solve()
{
	dijkstra(U, 0, 0), dijkstra(V, 1, 0);

	for(int i = 1; i <= n; i++) from_u[i][0] = from_u[i][1] = inf;

	from_u[S][0] = dist[S][0], from_u[T][1] = dist[T][0];

	dijkstra(S, 2, 1), dijkstra(T, 3, 2);

	for(int x = 1; x <= n; x++)
	{
		if(dist[x][2] + dist[x][3] == dist[T][2])

		ans = min(ans, min(from_u[x][0], from_u[x][1]) + dist[x][1]);
	}

	return min(ans, dist[V][0]);
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m>>S>>T>>U>>V;

	for(int i = 1, a, b, c; i <= m; i++)
	{
		cin>>a>>b>>c;

		grafo[a].push_back(pii(b, c));

		grafo[b].push_back(pii(a, c));
	}

	cout<<solve()<<"\n";
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, long long int, long long int)':
commuter_pass.cpp:27:23: warning: unused variable 'd' [-Wunused-variable]
   int x = pq.top().s, d = pq.top().f;
                       ^

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