Submission #683556

#	Time	Username	Problem	Language	Result	Execution time	Memory
683556		42kangaroo	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	648 ms	67976 KiB

commuter_pass

//
// Created by 42kangaroo on 17/01/2023.
//
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Edge {
	int fr, to, w;
};

struct nEdge {
	int to, w;
	int stat;
};

bool operator>(const Edge &l, const Edge &r) {
	return l.w > r.w;
}

bool operator>(const nEdge &l, const nEdge &r) {
	return l.w > r.w;
}

using g_t = vector<vector<Edge>>;

void dfs(int n, g_t &gr, g_t &outB, g_t &outF, vector<bool>& vis) {
	if (vis[n])return;
	vis[n] = true;
	for (auto e: gr[n]) {
		outB[n].push_back(e);
		outF[e.to].push_back({e.to, e.fr, 0});
		dfs(e.to, gr, outB, outF, vis);
	}
}

g_t dijkstra(g_t &gr, int s, int t) {
	vector<int> dist(gr.size(), -1);
	priority_queue<Edge, vector<Edge>, greater<>> q;
	q.push({s, s, 0});
	g_t back(gr.size());
	while (!q.empty()) {
		auto ed = q.top();
		q.pop();
		if (dist[ed.to] != -1 && dist[ed.to] < ed.w) continue;
		back[ed.to].push_back({ed.to, ed.fr, 0});
		if (dist[ed.to] == -1) {
			dist[ed.to] = ed.w;
			for (auto &e: gr[ed.to]) {
				auto ne = e;
				ne.w = ed.w + e.w;
				q.push(ne);
			}
		}
	}
	return back;
}

int dijkstradist(g_t &gr, g_t &ba, g_t &fr, int u, int v) {
	array<vector<int>, 4> d{};
	d.fill(vector<int>(gr.size(), -1));
	priority_queue<nEdge, vector<nEdge>, greater<>> q;
	q.push({u, 0, 0});
	while (!q.empty()) {
		auto ed = q.top();
		q.pop();
		if (ed.to == v) {
			return ed.w;
		}
		if (d[ed.stat][ed.to] != -1) continue;
		d[ed.stat][ed.to] = ed.w;
		for (auto e: gr[ed.to]) {
			if (ed.stat == 0) {
				q.push({e.to, e.w + ed.w, 0});
			} else {
				q.push({e.to, e.w + ed.w, 3});
			}
		}
		if (ed.stat < 2) {
			for (auto e: fr[ed.to]) {
				q.push({e.to, e.w + ed.w, 1});
			}
		}
		if (!(ed.stat & 1)) {
			for (auto e: ba[ed.to]) {
				q.push({e.to, e.w + ed.w, 2});
			}
		}
	}
	return -1;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	--s;
	--t;
	--u;
	--v;
	g_t gr(n);
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a;
		--b;
		gr[a].push_back({a, b, c});
		gr[b].push_back({b, a, c});
	}
	auto back = dijkstra(gr, s, t);
	g_t backR(n), frontR(n);
	vector<bool> vis(n, false);
	dfs(t, back, backR, frontR, vis);
	cout << dijkstradist(gr, backR, frontR, u, v) << "\n";
}

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