oj.uz

Submission #350693

# Submission time Handle Problem Language Result Execution time Memory
350693 2021-01-19T07:32:14 Z shivensinha4 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 409 ms 8436 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 = 1e15;

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 1004 KB Output is correct
2 Correct 10 ms 748 KB Output is correct
3 Correct 27 ms 876 KB Output is correct
4 Correct 31 ms 876 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 10 ms 748 KB Output is correct
7 Correct 1 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 33 ms 876 KB Output is correct
11 Correct 34 ms 876 KB Output is correct
12 Incorrect 33 ms 876 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 8428 KB Output is correct
2 Correct 409 ms 8172 KB Output is correct
3 Correct 316 ms 8436 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 24 ms 876 KB Output is correct
2 Correct 13 ms 748 KB Output is correct
3 Correct 235 ms 6636 KB Output is correct
4 Correct 10 ms 748 KB Output is correct
5 Correct 304 ms 8300 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 75 ms 8428 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 1004 KB Output is correct
2 Correct 10 ms 748 KB Output is correct
3 Correct 27 ms 876 KB Output is correct
4 Correct 31 ms 876 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 10 ms 748 KB Output is correct
7 Correct 1 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 33 ms 876 KB Output is correct
11 Correct 34 ms 876 KB Output is correct
12 Incorrect 33 ms 876 KB Output isn't correct
13 Halted 0 ms 0 KB -