Submission #1282378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282378		shirokito	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	171 ms	2052 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 24;
const ll INF = 1e18;

struct Edge {
	int u, v, c, d;
} E[N];

int n, m;
vector<int> g[2][N];
vector<ll> dist[2][2];
bool mp[N];

void gen_dist(int start, vector<ll> &d, bool rev) {
	d.assign(n + 1, INF);
	vector<int> vis(n + 1, 0), par(n + 1, 0);

	d[start] = 0;

	for (int _ = 0; _ < n; _++) {
		int u = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && (u == 0 || d[u] > d[i])) u = i;
		}

		vis[u] = 1;

		for (int i: g[rev][u]) {
			int v = u ^ E[i].u ^ E[i].v, w = E[i].c;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				par[v] = i;
			}
		}
	} 

	for (int u = 1; u <= n; u++) {
		if (par[u]) mp[par[u]] = 1;
	}
}

ll calc_dist(int start, int end) {
	vector<ll> d(n + 1, INF);
	vector<int> vis(n + 1, 0);

	d[start] = 0;

	for (int _ = 0; _ < n; _++) {
		int u = 0;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && (u == 0 || d[u] > d[i])) u = i;
		}

		vis[u] = 1;

		for (int i: g[0][u]) {
			int v = u ^ E[i].u ^ E[i].v, w = E[i].c;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
			}
		}
	} 

	return d[end];
}

void solve() {
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		auto &[u, v, c, d] = E[i]; 
		cin >> u >> v >> c >> d;
		g[0][u].push_back(i);
		g[1][v].push_back(i);
	}

	gen_dist(1, dist[0][0], 0);
	gen_dist(1, dist[0][1], 1);
	gen_dist(n, dist[1][0], 0);
	gen_dist(n, dist[1][1], 1);

	ll res = dist[0][0][n] + dist[1][0][1];

	for (int i = 1; i <= m; i++) {
		auto &[u, v, c, d] = E[i]; 
		if (!mp[i]) {
			ll dist_1n = min(dist[0][0][n], dist[0][0][v] + c + dist[1][1][u]);
			ll dist_n1 = min(dist[1][0][1], dist[1][0][v] + c + dist[0][1][u]);
			res = min(res, dist_1n + dist_n1 + d);
		}
		else {
			g[0][u].erase(find(g[0][u].begin(), g[0][u].end(), i));
			g[0][v].push_back(i);
			res = min(res, calc_dist(1, n) + calc_dist(n, 1) + d);
			g[0][v].pop_back();
			g[0][u].push_back(i);
		}
	}

	if (res >= INF) res = -1;

	cout << res << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

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