oj.uz

답안 #276499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -