Submission #1226569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226569		wedonttalkanymore	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	717 ms	35592 KiB

commuter_pass

#include <bits/stdc++.h>

#define pii pair <long long, long long>
#define fi first
#define se second

using namespace std;
using ll = long long;

const ll N = 200005, inf = 1e16;

int n, m, S, T, U, V;
vector <pii> adj[N];
ll dist_s[N], dist_t[N], dist_ans[N];
int a[N], b[N], c[N];
map <pair <int, int>, ll> mp;

void dijkstra(int x, ll *length) {
	for (int i = 1; i <= n; i++) length[i] = inf;
	length[x] = 0;
	priority_queue <pii, vector <pii>, greater <pii> > q;
	q.push({length[x], x});
	while(q.size()) {
		auto tmp = q.top();
		q.pop();
		ll u = tmp.se, z = tmp.fi;
		if (z > length[u]) continue;
		for (auto v : adj[u]) {
			if (length[v.fi] > length[u] + v.se) {
				length[v.fi] = length[u] + v.se;
				q.push({length[v.fi], v.fi});
			}
		}
	}
}

void dijkstra1() {
	for (int i = 1; i <= n; i++) dist_ans[i] = inf;
	dist_ans[U] = 0;
	priority_queue <pii, vector <pii>, greater <pii> > q;
	q.push({dist_ans[U], U});
	while(q.size()) {
		auto tmp = q.top();
		q.pop();
		ll u = tmp.se, z = tmp.fi;
		if (z > dist_ans[u]) continue;
		for (auto v : adj[u]) {
			int x = min(u, v.fi), y = max(u, v.fi);
			if (dist_ans[v.fi] > dist_ans[u] + mp[{x, y}]) {
				dist_ans[v.fi] = dist_ans[u] + mp[{x, y}];
				q.push({dist_ans[v.fi], v.fi});
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	cin >> S >> T;
	cin >> U >> V;
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].emplace_back(b[i], c[i]);
		adj[b[i]].emplace_back(a[i], c[i]);
	}
	
	dijkstra(S, dist_s);
	dijkstra(T, dist_t);
//	for (int i = 1; i <= n; i++) cout << dist_s[i] << ' ' << dist_t[i] << '\n';
	ll minn = dist_s[T]; // khoang cach ngan nhat tu s den t
	for (int i = 1; i <= m; i++) {
		int x = min(a[i], b[i]);
		int y = max(a[i], b[i]);
		if ((dist_s[a[i]] + c[i] + dist_t[b[i]] == minn) || (dist_s[b[i]] + c[i] + dist_t[a[i]] == minn)) {
			int x = min(a[i], b[i]);
			int y = max(a[i], b[i]);
			mp[{x, y}] = 0;
		}
		else mp[{x, y}] = c[i];
//		cout << a[i] << ' ' << b[i] << ' ' << mp[{x, y}] << '\n';
	}
	dijkstra1();
	cout << dist_ans[V];
	return 0;
}

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