oj.uz

Submission #350696

# Submission time Handle Problem Language Result Execution time Memory
350696 2021-01-19T07:34:10 Z shivensinha4 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 391 ms 7532 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 10 ms 748 KB Output is correct
3 Correct 27 ms 876 KB Output is correct
4 Correct 32 ms 876 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 12 ms 748 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 32 ms 876 KB Output is correct
11 Correct 39 ms 748 KB Output is correct
12 Incorrect 34 ms 748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 7404 KB Output is correct
2 Correct 391 ms 7276 KB Output is correct
3 Correct 376 ms 7404 KB Output is correct
4 Incorrect 26 ms 1004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1024 KB Output is correct
2 Correct 10 ms 748 KB Output is correct
3 Correct 292 ms 5868 KB Output is correct
4 Correct 10 ms 748 KB Output is correct
5 Correct 364 ms 7404 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Incorrect 76 ms 7532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 10 ms 748 KB Output is correct
3 Correct 27 ms 876 KB Output is correct
4 Correct 32 ms 876 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 12 ms 748 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 32 ms 876 KB Output is correct
11 Correct 39 ms 748 KB Output is correct
12 Incorrect 34 ms 748 KB Output isn't correct
13 Halted 0 ms 0 KB -