Submission #350696

#	Time	Username	Problem	Language	Result	Execution time	Memory
350696		shivensinha4	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	391 ms	7532 KiB

ho_t4

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

/*
 * Mark edges in the shortest-path tree with source as 0 and then n-1.
 * Run floyd-warshall.
 * ans = dist[0][n-1]
 * For each edge (u -> v):
 *   if it is in any tree:
 *     run dijkstra from 0 and then from n-1 excluding this edge (newDist)
 *     ans = min(ans, newDist[0][n-1] + newdist[n-1][v] + w + c + dist[u][0])
 *     (dist[u][0] can use this edge in its initial direction, but then it would be better
 *     to go directly from v -> 0 rather than going to u first, and the initial answer would be better itself)
 *   else:
 *     ans = min(ans, dist[0][n-1] + dist[n-1][v] + w + c + dist[u][0])
 *     (again same argument for why dist[u][0] can be used)
 */


int n, m;
vector<vector<vector<ll>>> adj;
const ll INF = 1e16;

void dijk(int s, vi &pre, vector<ll> &dist, int del=-1) {
	dist[s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
	pq.push({0, s});
	while (pq.size()) {
		int p = pq.top().second; ll d = pq.top().first; pq.pop();
		if (dist[p] != d) continue;
		for (auto &i: adj[p]) if (i[2] != del and dist[i[0]] > i[1]+d) {
			pre[i[0]] = i[2];
			dist[i[0]] = i[1]+d;
			pq.push({dist[i[0]], i[0]});
		}
	}
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	adj.resize(n);
	vector<vector<ll>> edges(m);
	vector<vector<ll>>dist(n, vector<ll>(n, INF));
	
	for_(i, 0, n) dist[i][i] = 0;

	for_(i, 0, m) {
		int a, b; ll d, c; cin >> a >> b >> d >> c;
		a -= 1; b -= 1;
		edges[i] = {a, b, d, c, i};
		adj[a].push_back({b, d, i});
		dist[a][b] = min(dist[a][b], d);
	}

	for_(k, 0, n) for_(i, 0, n) for_(j, 0, n) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
	vector<vector<ll>> currDist(2, vector<ll>(n, INF));
	vi pre(n, -1);
	vector<bool> used(m);

	dijk(0, pre, currDist[0]);
	for_(i, 0, n) if (pre[i] != -1) used[pre[i]] = true;

	pre.assign(n, -1);
	dijk(n-1, pre, currDist[1]);
	for_(i, 0, n) if (pre[i] != -1) used[pre[i]] = true;
	
	ll ans = dist[0][n-1]+dist[n-1][0];
	for_(i, 0, n) assert(dist[0][i] == currDist[0][i] and dist[n-1][i] == currDist[1][i]);
	
	for_(i, 0, m) {
		int u = edges[i][0], v = edges[i][1], idx = edges[i][4]; ll d = edges[i][2], c = edges[i][3];
		if (used[idx]) {
			currDist.assign(2, vector<ll>(n, INF));
			dijk(0, pre, currDist[0], i);
			dijk(n-1, pre, currDist[1], i);
			ans = min(ans, currDist[0][n-1] + currDist[1][v] + d + c + dist[u][0]);
		} else ans = min(ans, dist[0][n-1] + dist[n-1][v] + d + c + dist[u][0]);
	}
	
	cout << (ans >= INF ? -1 : ans) << endl;


	return 0;
}

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