Submission #850587

#	Time	Username	Problem	Language	Result	Execution time	Memory
850587		Qang	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	109 ms	262144 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, s, t, u, v;
void dijkstra(ll source, ll dest, vector<vector<ll>> &g, bool flag) {
	vector<ll> dist(n + 1, INT_MAX);
	vector<bool> visited(n + 1, false);
	vector<ll> parent(n + 1, -1);
	dist[source] = 0;
	priority_queue<pair<ll, ll>> q;
	q.push({ 0, source });
	while (!q.empty()) {
		auto curr = q.top();
		q.pop();
		if (visited[curr.second]) continue;
		visited[curr.second] = true;
		for (int i = 1; i <= n; ++i) {
			ll adj = g[curr.second][i];
			if (adj != INT_MAX && dist[curr.second] + adj < dist[i]) {
				dist[i] = dist[curr.second] + adj;
				q.push({ -dist[i], i });
				parent[i] = curr.second;
			}
		}
	}
	if (!flag) {
		ll tmp = dest;
		while (parent[tmp] != -1) {
			g[tmp][parent[tmp]] = 0;
			g[parent[tmp]][tmp] = 0;
			tmp = parent[tmp];
		}
	}
	else cout << dist[dest];
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> s >> t >> u >> v;
	vector<vector<ll>> g(n + 1, vector<ll>(n + 1, INT_MAX));
	for (int i = 0; i <= n; ++i)
		g[i][i] = 0;
	for (int i = 0; i < m; ++i) {
		ll a, b, c;
		cin >> a >> b >> c;
		g[a][b] = min(g[a][b], c);
		g[b][a] = min(g[b][a], c);
	}
	dijkstra(s, t, g, 0);
	dijkstra(u, v, g, 1);
}

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