Submission #229663

#	Time	Username	Problem	Language	Result	Execution time	Memory
229663		hanagasumi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	796 ms	41700 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;

int inf = 1e18 + 100;

struct edge {
	int u, w, num;
	edge(int _u, int _w, int _num) : u(_u), w(_w), num(_num) {}
};

vector<vector<edge>> g;

vector<int> djkstra(int n, int st) {
	vector<int> d(n, inf);
	d[st] = 0;
	set<pair<int, int>> now;
	now.insert({0, st});
	while(len(now) > 0) {
		auto rasm = *now.begin();
		now.erase(rasm);
		for (auto x : g[rasm.sc]) {
			if(d[x.u] <= rasm.ft + x.w) 
				continue;
			now.erase({d[x.u], x.u});
			d[x.u] = rasm.ft + x.w;
			now.insert({d[x.u], x.u});
		}
	}
	return d;
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m, st, fn, st2, fn2;
	cin >> n >> m;
	cin >> st >> fn >> st2 >> fn2;
	st--, fn--, st2--, fn2--;
	g = vector<vector<edge>> (n);
	vector<bool> good(m, 0);
	vector<pair<pair<int, int>, int>> have;
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		g[a].pb({b, w, i});
		g[b].pb({a, w, i});
		have.pb({{a, b}, w});
	}

	auto dst_st = djkstra(n, st);
	auto dst_fn = djkstra(n, fn);
	int min_dst = dst_st[fn];
	// cout << min_dst << endl;
	for (int i = 0; i < m; i++) {
		if(dst_st[have[i].ft.ft] + dst_fn[have[i].ft.sc] + have[i].sc == min_dst)
			good[i] = 1;
		if(dst_fn[have[i].ft.ft] + dst_st[have[i].ft.sc] + have[i].sc == min_dst) 
			good[i] = 1;
		// cout << i << " " << good[i] << endl;
	}

	int d[n][4];
	for (int i = 0; i < n; i++) {
		d[i][0] = d[i][1] = d[i][2] = d[i][3] = inf;
	}
	d[st2][0] = 0;
	set<pair<int, pair<int, int>>> q;
	q.insert({0, {st2, 0}});
	while(len(q) > 0) {
		auto rasm = *q.begin();
		// cout << rasm.sc.ft << " " << rasm.sc.sc << " " << rasm.ft << endl;
		q.erase(rasm);
		if(rasm.sc.sc == 0) {
			for (int j = 1; j < 4; j++) {
				if(d[rasm.sc.ft][j] > rasm.ft) {
					q.erase({d[rasm.sc.ft][j], {rasm.sc.ft, j}});
					d[rasm.sc.ft][j] = rasm.ft;
					q.insert({d[rasm.sc.ft][j], {rasm.sc.ft, j}});
				}
			}
		}
		if(rasm.sc.sc == 1 || rasm.sc.sc == 2) {
			if(d[rasm.sc.ft][3] > rasm.ft) {
				q.erase({d[rasm.sc.ft][3], {rasm.sc.ft, 3}});
				d[rasm.sc.ft][3] = rasm.ft;
				q.insert({d[rasm.sc.ft][3], {rasm.sc.ft, 3}});
			}
		}
		for (auto x : g[rasm.sc.ft]) {
			if(rasm.sc.sc == 1) {
				if(!good[x.num]) 
					continue;
				if(dst_st[x.u] > dst_st[rasm.sc.ft]) 
					continue;
				if(d[x.u][1] > rasm.ft) {
					q.erase({d[x.u][1], {x.u, 1}});
					d[x.u][1] = rasm.ft;
					q.insert({d[x.u][1], {x.u, 1}});
				}
				continue;
			}
			if(rasm.sc.sc == 2) {
				if(!good[x.num])
					continue;
				if(dst_st[x.u] < dst_st[rasm.sc.ft]) 
					continue;
				if(d[x.u][2] > rasm.ft) {
					q.erase({d[x.u][2], {x.u, 2}});
					d[x.u][2] = rasm.ft;
					q.insert({d[x.u][2], {x.u, 2}});
				}
				continue;
			}
			if(d[x.u][rasm.sc.sc] > rasm.ft + x.w) {
				q.erase({d[x.u][rasm.sc.sc], {x.u, rasm.sc.sc}});
				d[x.u][rasm.sc.sc] = rasm.ft + x.w;
				q.insert({d[x.u][rasm.sc.sc], {x.u, rasm.sc.sc}});
			}
		}
	}
	cout << d[fn2][3] << endl;
}

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