Submission #1038370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038370		kfhjad	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	166 ms	24556 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<pair<int, int>> adj[100001];

void dijkstra(int X, auto& minCostX)
{
	using E = pair<ll, int>;
	priority_queue<E, vector<E>, greater<E>> q;
	q.push({0, X});

	while (!q.empty())
	{
		auto [cost, node] = q.top();
		q.pop();
		
		if (cost != minCostX[node])
			continue;
		
		for (auto [i, x] : adj[node])
		{
			if (cost + x < minCostX[i])
				q.push({minCostX[i] = cost + x, i});
		}
	}
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
	int N, M, S, T, U, V;
	cin >> N >> M >> S >> T >> U >> V;
	vector<ll> minCostS(N + 1, LLONG_MAX), minCostU(N + 1, LLONG_MAX), minCostV(N + 1, LLONG_MAX);
	minCostS[S] = minCostU[U] = minCostV[V] = 0;
	
	while (M--)
	{
		int a, b, x;
		cin >> a >> b >> x;
		
		adj[a].push_back({b, x});
		adj[b].push_back({a, x});
	}
	
	dijkstra(S, minCostS);
	dijkstra(U, minCostU);
	dijkstra(V, minCostV);

	
	vector<bool> visited(N + 1);
	queue<int> q;
	q.push(T);
	vector<vector<int>> DAG(N + 1), rDAG(N + 1);
	vector<int> indegree(N + 1), rIndegree(N + 1);
	
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		
		for (auto [i, x] : adj[node])
			if (minCostS[i] + x == minCostS[node])
			{	
				if (!visited[i])
					q.push(i), visited[i] = true;

				DAG[i].push_back(node), rDAG[node].push_back(i);
				++indegree[node], ++rIndegree[i];
			}
	}
	
	vector<ll> RminU = minCostU;
	vector<ll> RminV = minCostV;
	
	q.push(T);
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		
		for (auto i : rDAG[node])	
		{
			if (--rIndegree[i] == 0)
				q.push(i);
			
			RminU[i] = min(RminU[i], RminU[node]);
			RminV[i] = min(RminV[i], RminV[node]);
		}
	}
	
	ll ans = LLONG_MAX;
	
	q.push(S);
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		
		ans = min(ans, minCostU[node] + RminV[node]);
		ans = min(ans, minCostV[node] + RminU[node]);
		
		for (auto i : DAG[node])	
		{
			if (--indegree[i] == 0)
				q.push(i);
			
			minCostU[i] = min(minCostU[i], minCostU[node]);
			minCostV[i] = min(minCostV[i], minCostV[node]);
		}
	}
	
	cout << min(minCostU[V], ans) << endl;
		
    return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

commuter_pass.cpp:8:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | void dijkstra(int X, auto& minCostX)
      |                      ^~~~

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