제출 #1038325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038325		kfhjad	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	163 ms	13764 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<pair<int, int>> adj[100001];
ll minCostS[100001], minCostU[100001], minCostV[100001];

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
	int N, M, S, T, U, V;
	cin >> N >> M >> S >> T >> U >> V;
	
	for (int i = 0; i <= N; ++i)
		minCostS[i] = minCostU[i] = minCostV[i] = 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});
	}
	
	using E = pair<ll, int>;
	priority_queue<E, vector<E>, greater<E>> q;
	q.push({0, S});

	while (!q.empty())
	{
		auto [cost, node] = q.top();
		q.pop();
		
		if (cost != minCostS[node])
			continue;
		
		for (auto [i, x] : adj[node])
		{
			if (cost + x < minCostS[i])
				q.push({minCostS[i] = cost + x, i});
		}
	}
	
	vector<bool> visited(N + 1), commuter(N + 1);
	queue<int> qq;
	qq.push(T);
	
	while (!qq.empty())
	{
		int node = qq.front();
		qq.pop();
		
		visited[node] = commuter[node] = true;
		
		for (auto [i, x] : adj[node])
			if (minCostS[i] + x == minCostS[node] && !visited[i])
				qq.push(i), visited[i] = true;
	}
	
	ll minU = LLONG_MAX, minV = LLONG_MAX;

	q.push({0, U});
	while (!q.empty())
	{
		auto [cost, node] = q.top();
		q.pop();
		
		if (cost != minCostU[node])
			continue;
			
		if (commuter[node])
			minU = min(minU, cost);

		for (auto [i, x] : adj[node])
		{
			if (cost + x < minCostU[i])
				q.push({minCostU[i] = cost + x, i});
		}
	}
	
	q.push({0, V});
	while (!q.empty())
	{
		auto [cost, node] = q.top();
		q.pop();
		
		if (cost != minCostV[node])
			continue;
		
		if (commuter[node])
			minV = min(minV, cost);

		for (auto [i, x] : adj[node])
		{
			if (cost + x < minCostV[i])
				q.push({minCostV[i] = cost + x, i});
		}
	}
	
	cout << min(minCostU[V], minU + minV) << 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
 */

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