Submission #682118

#	Time	Username	Problem	Language	Result	Execution time	Memory
682118		ethening	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	358 ms	30396 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

ll INF = 1000'000'000'000'000'000ll;

struct edge {
	int fr, to;
	ll we;
};

struct pqnode {
	ll cDist;
	int node;
};

void dijkstra(int n, const vector<vector<edge>>& E, int S, vector<ll>& dist) {
	auto cmp = [](const pqnode& u, const pqnode& v) {
		return u.cDist > v.cDist;
	};
	priority_queue<pqnode, vector<pqnode>, decltype(cmp)> Q(cmp);
	dist = vector<ll>(n + 5, INF);
	dist[S] = 0;
	Q.push({.cDist = 0, .node = S});
	while (!Q.empty()) {
		auto [cDist, node] = Q.top();
		Q.pop();
		if (cDist > dist[node]) continue;
		for (auto [fr, to, we] : E[node]) {
			if (dist[fr] + we < dist[to]) {
				dist[to] = dist[fr] + we;
				Q.push({.cDist = dist[to], .node = to});
			}
		}
	}
}

void dagDp(int cur, const vector<vector<edge>>& G, const vector<ll>& uDist, const vector<ll>& vDist, vector<ll>& dist1, vector<ll>& dist2) {
	dist1[cur] = uDist[cur];
	dist2[cur] = vDist[cur];
	for (auto [fr, to, we]: G[cur]) {
		if (dist1[to] == -1) {
			dagDp(to, G, uDist, vDist, dist1, dist2);
		}
		dist1[cur] = min(dist1[cur], dist1[to]);
		dist2[cur] = min(dist2[cur], dist2[to]);
	}	
	// cout << cur << "  : "<< dist1[cur] << " " << dist2[cur] << endl;
}

int main() {
	int n, m;
	int s, t, u, v;
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> s >> t >> u >> v;
	
	vector<vector<edge>> E(n + 5, vector<edge>());
	for (int i = 1; i <= m; i++) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		E[a].push_back({.fr = a, .to = b, .we = c});
		E[b].push_back({.fr = b, .to = a, .we = c});
	}

	vector<ll> sDist;
	dijkstra(n, E, s, sDist);
	vector<ll> tDist;
	dijkstra(n, E, t, tDist);
	vector<ll> uDist;
	dijkstra(n, E, u, uDist);
	vector<ll> vDist;
	dijkstra(n, E, v, vDist);

	// for (int i = 1; i <= n; i++) {
	// 	cout << "i: " << i << " s: " << sDist[i] << " t: " << tDist[i];
	// 	cout << " u: " << uDist[i] << " v: " << vDist[i] << endl; 
	// }

	vector<vector<edge>> G(n + 5, vector<edge>());
	for (int i = 1; i <= n; i++) {
		for (auto [fr, to, we]: E[i]) {
			if (sDist[fr] + we + tDist[to] == sDist[t]) {
				G[fr].push_back({.fr = fr, .to = to, .we = 0});
			}
		}
	}

	vector<ll> dist1(n + 5, -1);
	vector<ll> dist2(n + 5, -1);
	dagDp(s, G, uDist, vDist, dist1, dist2);

	ll ans = uDist[v];
	for (int i = 1; i <= n; i++) {
		if (dist1[i] != -1) {
			ans = min(ans, min(dist1[i] + vDist[i], dist2[i] + uDist[i]));
		}
	}
	cout << ans << endl;
}

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