oj.uz

Submission #276499

# Submission time Handle Problem Language Result Execution time Memory
276499 2020-08-20T13:15:46 Z islingr Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 4212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1272 KB Output is correct
2 Correct 27 ms 1152 KB Output is correct
3 Correct 33 ms 1260 KB Output is correct
4 Correct 33 ms 1272 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 27 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 83 ms 1304 KB Output is correct
11 Correct 93 ms 1272 KB Output is correct
12 Incorrect 91 ms 1272 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 4152 KB Output is correct
2 Correct 225 ms 4212 KB Output is correct
3 Correct 197 ms 4156 KB Output is correct
4 Correct 33 ms 1272 KB Output is correct
5 Correct 31 ms 1152 KB Output is correct
6 Correct 28 ms 1152 KB Output is correct
7 Correct 29 ms 1152 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1284 KB Output is correct
2 Correct 28 ms 1152 KB Output is correct
3 Execution timed out 1061 ms 2652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1272 KB Output is correct
2 Correct 27 ms 1152 KB Output is correct
3 Correct 33 ms 1260 KB Output is correct
4 Correct 33 ms 1272 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 27 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 83 ms 1304 KB Output is correct
11 Correct 93 ms 1272 KB Output is correct
12 Incorrect 91 ms 1272 KB Output isn't correct
13 Halted 0 ms 0 KB -