Submission #500104

#	Time	Username	Problem	Language	Result	Execution time	Memory
500104		buidangnguyen05	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	289 ms	15688 KiB

commuter_pass

/* input

*/

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

typedef long long ll;
const int N = 1e5 + 10;
int n, m;
vector<pair<int, int>> adj[N];

pair<vector<ll>, vector<int>> dijkstra(int s) {
	vector<ll> d(n + 2, 1e15); vector<int> order;

	d[s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
	q.push(make_pair(d[s], s));

	while(!q.empty()) {
		ll dist; int x; tie(dist, x) = q.top(); q.pop();
		if(dist != d[x]) continue;
		order.push_back(x);
		for(pair<int, int> i : adj[x]) {
			int v, w; tie(v, w) = i;
			if(d[v] > d[x] + w) {
				d[v] = d[x] + w;
				q.push(make_pair(d[v], v));
			}
		}
	}

	return make_pair(d, order);
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	//freopen("task.inp", "r", stdin);
	//freopen("task.out", "w", stdout);

	int s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
	for(int i = 1; i <= m; ++i) {
		int x, y, w; cin >> x >> y >> w;
		adj[x].push_back(make_pair(y, w));
		adj[y].push_back(make_pair(x, w));
	}

	vector<ll> fu = dijkstra(u).first;
	vector<ll> fv = dijkstra(v).first;
	vector<ll> ft = dijkstra(t).first;
	vector<ll> fs; vector<int> order; 
	tie(fs, order) = dijkstra(s);

	ll res = fu[v];
	for(int turn = 0; turn < 2; ++turn) {
		vector<ll> f(n + 2, 1e15);
		f[s] = fu[s];
		for(int x : order) {
			if(fs[x] + ft[x] != fs[t]) continue;
			res = min(res, f[x] + fv[x]);
			for(pair<int, int> e : adj[x]) {
				int i, w; tie(i, w) = e;
				if(fs[i] + ft[i] != fs[t]) continue;
				f[i] = min(f[i], f[x]); f[i] = min(f[i], fu[x]);
			}
		}
		fu.swap(fv);
	}

	cout << res << "\n";
}

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