제출 #1155291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155291		pinbu	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	126 ms	6324 KiB

ho_t4

// F*ck this problem
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 202, M = 50005, oo = 1e12;
void mini(int &X, int Y) {
	if (X > Y) X = Y; 
}

int n, m;
vector<array<int, 3>> Adj[N], rAdj[N];
array<int, 4> e[M];
int d1[N], rdn[N], rd1[N], dn[N];
bool on[2][M];
void Dijkstra(int st, vector<array<int, 3>> *adj, int *d, int t) {
	fill(d + 1, d + 1 + n, oo);
	d[st] = 0;
	priority_queue<pair<int, int>> pq;
	pq.emplace(0, st);
	vector<int> prv(n + 1);
	while (pq.size()) {
		int u, di; tie(di, u) = pq.top();
		di = -di;
		pq.pop();
		if (d[u] != di) continue;
		for (auto V: adj[u]) {
			int v, w, id; tie(v, w, id) = {V[0], V[1], V[2]};
			if (d[v] > di + w) {
				if (t >= 0) prv[v] = id;
				pq.emplace(-(d[v] = di + w), v);
			}
		}
	}
	if (t >= 0 && d[n + 1 - st] < oo) {
		for (int cur = n + 1 - st; cur != st; cur = e[prv[cur]][0]) {
			on[t][prv[cur]] = true;
		}
		// I traced one shortest path from 1 to n and n to 1
	}
}
vector<int> l1, ln; vector<bool> vis;
int Dijkstra_recalc(int id) {
	fill(l1.begin(), l1.end(), oo);
	l1[1] = 0;
	fill(vis.begin(), vis.end(), false);
	for (int t = 1; t <= n; t++) {
		pair<int, int> best = {oo, -1};
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				best = min(best, {l1[i], i});
			}
		}
		if (best.second < 0) break;
		int u = best.second;
		vis[u] = true;
		if (e[id][1] == u) {
			int v = e[id][0], w = e[id][2];
			mini(l1[v], l1[u] + w);
		}
		for (auto V: Adj[u]) {
			if (V[2] == id) continue;
			int v, w; tie(v, w) = {V[0], V[1]};
			mini(l1[v], l1[u] + w);
		}
	}
	fill(ln.begin(), ln.end(), oo);
	ln[n] = 0;
	fill(vis.begin(), vis.end(), false);
	for (int t = 1; t <= n; t++) {
		pair<int, int> best = {oo, -1};
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) {
				best = min(best, {ln[i], i});
			}
		}
		if (best.second < 0) break;
		int u = best.second;
		vis[u] = true;
		if (e[id][1] == u) {
			int v = e[id][0], w = e[id][2];
			mini(ln[v], ln[u] + w);
		}
		for (auto V: Adj[u]) {
			if (V[2] == id) continue;
			int v, w; tie(v, w) = {V[0], V[1]};
			mini(ln[v], ln[u] + w);
		}
	}
	return l1[n] + ln[1];
}

void solve(void) {
	cin >> n >> m;
	for (int i = 1, a, b, c, d; i <= m; i++) {
		cin >> a >> b >> c >> d;
		 Adj[a].push_back({b, c, i});
		rAdj[b].push_back({a, c, i});
		e[i] = {a, b, c, d};
	}
	Dijkstra(1, Adj, d1, 0); Dijkstra(n, rAdj, rdn, -1);
	Dijkstra(n, Adj, dn, 1); Dijkstra(1, rAdj, rd1, -1);
	int ans = d1[n] + dn[1];
	l1.resize(n + 1); ln = l1; vis.resize(n + 1);
	for (int i = 1; i <= m; i++) {
		int d = e[i][3];
		if (on[0][i] || on[1][i]) {
			mini(ans, Dijkstra_recalc(i) + d);
			// I will just use Dijkstra's algo to recalculate if it is an edge I have traced before
		} else {
			int u = e[i][0], v = e[i][1], c = e[i][2];
			mini(ans, min(d1[v] + c + rdn[u], d1[n]) + min(dn[v] + c + rd1[u], dn[1]) + d);
		}
	}
	/*
	Proof: If an edge (u, v) is NOT on the shortest path from 1 to n (similar to from n to 1), it might be
	either on the shortest-path tree rooted at 1 or not. If not, it is obvious to see it, but if it is,
	d(1, v) >= d(1, u). Thus, we have d(1, v) + d(u, n) >= d(1, u) + d(u, n) >= d(1, n).
	*/
	/*
	Comment: If you find it hard to understand that algo, you can use Dijkstra's algo to recalculate if that edge
	is on either the shortest-path tree rooted at 1 or the shortest-path tree rooted at n.
	*/
	if (ans >= oo) ans = -1;
	cout << ans;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int TEST = 1;
    while (TEST--) solve();
    
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63