Submission #1226624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226624		wedonttalkanymore	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	672 ms	71524 KiB

commuter_pass

#include <bits/stdc++.h>

#define int long long
#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][3];
int a[N], b[N], c[N];

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});
			}
		}
	}
}

struct item {
	ll val, x, pre;
	bool operator <(const item &other) const {
		return val > other.val;
	}
};

struct node {
	ll u, w, type;
};
vector <node> adj1[N], adj2[N];
void dijkstra1(int root, vector <node> adj_x[]) {
	for (int i = 1; i <= n; i++) for (int j = 0; j < 3; j++) dist_ans[i][j] = inf;
	dist_ans[root][0] = 0;
	priority_queue <item> q;
	q.push({dist_ans[root][0], root, 0});
	while(q.size()) {
		auto tmp = q.top();
		q.pop();
		ll val = tmp.val, u = tmp.x, pre = tmp.pre;
		if (val > dist_ans[u][pre]) continue;
		
		for (auto v : adj_x[u]) {
			int x = min(u, v.u), y = max(u, v.u);
			if (pre == 0) {
				if (dist_ans[v.u][0] > dist_ans[u][pre] + v.w) { // tiep tuc ko dung ve va di tiep
					dist_ans[v.u][0] = dist_ans[u][pre] + v.w;
					q.push({dist_ans[v.u][0], v.u, 0});
				}
				if (v.type == 0 && dist_ans[v.u][1] > dist_ans[u][pre]) { // bat dau dung ve
					dist_ans[v.u][1] = dist_ans[u][pre];
					q.push({dist_ans[v.u][1], v.u, 1});
				}
			}
			
			else if (pre == 1) {
				if (v.type == 0 && dist_ans[v.u][1] > dist_ans[u][pre]) {
					dist_ans[v.u][1] = dist_ans[u][pre];
					q.push({dist_ans[v.u][1], v.u, 1});
				}
				if (dist_ans[v.u][2] > dist_ans[u][pre] + v.w) { // ko dung ve nua
					dist_ans[v.u][2] = dist_ans[u][pre] + v.w;
					q.push({dist_ans[v.u][2], v.u, 2});
				}
			}
			
			else if (pre == 2) {
				if (dist_ans[v.u][2] > dist_ans[u][pre] + v.w) {
					dist_ans[v.u][2] = dist_ans[u][pre] + v.w;
					q.push({dist_ans[v.u][2], v.u, 2});
				}
			}
		}
	}
}

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 u = a[i], v = b[i];
	    bool free_uv = (dist_s[u] + c[i] + dist_t[v] == minn);
	    bool free_vu = (dist_s[v] + c[i] + dist_t[u] == minn);
	    
	    adj1[u].push_back({v, c[i], free_uv ? 0 : -1});
	    adj1[v].push_back({u, c[i], free_vu ? 0 : -1});
	
	    adj2[u].push_back({v, c[i], free_vu ? 0 : -1});
	    adj2[v].push_back({u, c[i], free_uv ? 0 : -1});
	}

	dijkstra1(U, adj1);
	ll x = min({dist_ans[V][0], dist_ans[V][1], dist_ans[V][2]});
//	cout << dist_ans[V][0] << ' ' << dist_ans[V][1] << ' ' << dist_ans[V][2] << '\n';
	dijkstra1(U, adj2);
	ll y = min({dist_ans[V][0], dist_ans[V][1], dist_ans[V][2]});
//	cout << dist_ans[V][0] << ' ' << dist_ans[V][1] << ' ' << dist_ans[V][2] << '\n';
	cout << min(x, y);
	return 0;
}

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