Submission #541391

#	Time	Username	Problem	Language	Result	Execution time	Memory
541391		_karan_gandhi	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	392 ms	38168 KiB

commuter_pass

// subtask 2

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

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

ll int inf = 1e16;

void solve() {
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int U, V; cin >> U >> V;
	s--; t--; U--; V--;

	vector<vector<pair<int, ll int>>> adj(n);
	// vector<vector<ll int>> wt(n, vector<ll int>(n, inf)); // here so optimise this

	for (int i = 0; i < m; i++) {
		int a, b; ll int c; cin >> a >> b >> c;
		a--; b--;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}

	{
		vector<int> came_from(n, -1);
		vector<ll int> dist(n, inf);
		dist[s] = 0;
		priority_queue<pair<ll int, int>> pq;
		pq.emplace(0, s);

		while (pq.size() != 0) {
			int u = pq.top().second;
			ll int cur_dist = pq.top().first * -1;
			pq.pop();

			if (dist[u] != cur_dist) continue;

			for (auto [v, cost] : adj[u]) {
				ll int new_dist = cur_dist + cost;
				
				if (new_dist < dist[v]) {
					dist[v] = new_dist;
					came_from[v] = u;
					pq.emplace(-new_dist, v);
				}
			}
		}

		assert(came_from[t] != -1);
		
		map<pair<int, int>, bool> ignore;

		int node = t;
		while (node != -1) {
			int prev = came_from[node];
			if (prev == -1) break;

			ignore[{prev, node}] = 1;
			ignore[{node, prev}] = 1;

			node = prev;
		}

		vector<vector<pair<int, ll int>>> new_adj(n);

		for (int i = 0; i < n; i++) {
			// new_adj[i].emplace_back(a)
			for (auto [v, _] : adj[i]) {
				if (ignore.count({i, v}) != 0) {
					new_adj[i].emplace_back(v, 0);
				} else {
					new_adj[i].emplace_back(v, _);
				}
			}
		}

		adj = new_adj;
	}

	// now run a djkstra from U to V
	vector<ll int> dist(n, inf);
	dist[U] = 0;
	priority_queue<pair<ll int, int>> pq;
	pq.emplace(0, U);

	while (pq.size() != 0) {
		int u = pq.top().second;
		ll int cur_dist = pq.top().first * -1;
		pq.pop();

		for (auto [v, cost] : adj[u]) {
			ll int new_dist = cur_dist + cost;

			if (new_dist < dist[v]) {
				dist[v] = new_dist;
				pq.emplace(-new_dist, v);
			}
		}
	}

	// assert(dist[V] < inf);

	cout << dist[V] << endl;
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

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