Submission #276499

#	Time	Username	Problem	Language	Result	Execution time	Memory
276499		islingr	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1061 ms	4212 KiB

ho_t4

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

#pragma GCC optimize ("trapv")

using ll = long long;

template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int N = 1 << 9, M = 1 << 16;
const ll inf = 1e18;

int n;
ll d[N][N];
int a[M], b[M], w[M], c[M];
vector<int> g[N];
bool onPath[M], vis[N];

bool dfs(int u, int t) {
	if (u == t) return true;
	vis[u] = true;
	for (int e : g[u]) {
		assert(a[e] == u);
		int v = b[e];
		if (!vis[v] && w[e] + d[v][t] == d[u][t] && dfs(v, t))
			return onPath[e] = true;
	}
	return false;
}

ll dist[N];
ll dij(int s, int t) {
	fill(dist, dist + n, inf);
	priority_queue<pair<ll, int>> pq;
	pq.push({0, s});
	while (!pq.empty()) {
		int u = pq.top().second;
		if (dist[u] == inf) {
			dist[u] = -pq.top().first;
			for (int e : g[u]) {
				int v = u != a[e] ? a[e] : b[e];
				pq.push({-(dist[u] + w[e]), v});
			}
		} else assert(!ckmin(dist[u], -pq.top().first));
		pq.pop();
	}
	return dist[t];
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int m; cin >> n >> m;
	rep(u, 0, n) rep(v, 0, n) d[u][v] = inf;
	rep(i, 0, n) d[i][i] = 0;
	rep(e, 0, m) {
		cin >> a[e] >> b[e] >> w[e] >> c[e], --a[e], --b[e];
		ckmin(d[a[e]][b[e]], ll(w[e]));
		g[a[e]].push_back(e);
	}

	rep(w, 0, n)
		rep(u, 0, n)
			rep(v, 0, n)
				ckmin(d[u][v], d[u][w] + d[w][v]);

	fill(vis, vis + n, 0); dfs(0, n - 1);
	fill(vis, vis + n, 0); dfs(n - 1, 0);

	ll ans = d[0][n - 1] + d[n - 1][0];
	rep(e, 0, m) {
		if (!onPath[e]) {
			ll to = min(d[0][n - 1], d[0][b[e]] + w[e] + d[a[e]][n - 1]);
			ll fr = min(d[n - 1][0], d[n - 1][b[e]] + w[e] + d[a[e]][0]);
			ckmin(ans, c[e] + to + fr);
		} else {
			swap(a[e], b[e]);
			ckmin(ans, c[e] + dij(0, n - 1) + dij(n - 1, 0));
			swap(a[e], b[e]);
		}
	}
	cout << (ans < inf ? ans : -1);
}

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