oj.uz

답안 #854436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854436 2023-09-27T16:22:38 Z QuangBui Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 311 ms 25296 KB 
// QuangBuiCP
// 375.cpp
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "local/debug.hpp"
#else
#define debug(...)
#endif // LOCAL

#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()

#define int long long

struct State {
	int x;
	int dist;
	bool operator < (const State& other) const {
		return dist > other.dist;
	}
};

vector<int> run_dijkstra(int n, const vector<vector<pair<int, int>>>& g, int start) {
	vector<int> dist(n, LLONG_MAX / 2);
	priority_queue<State> pq;
	pq.push({start, 0});
	dist[start] = 0;
	while (SZ(pq)) {
		State top = pq.top(); pq.pop();
		int u = top.x;
		int cur = top.dist;
		if (dist[u] != cur) {
			continue;
		}
		for (auto& p : g[u]) {
			int v = p.first;
			int w = p.second;
			if (cur + w < dist[v]) {
				dist[v] = cur + w;
				pq.push({v, dist[v]});
			}
		}
	}
	return dist;
}

signed main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

	int n, m;
	cin >> n >> m;
	int S, T, X, Y;
	cin >> S >> T >> X >> Y; S--, T--, X--, Y--;
	vector<vector<pair<int, int>>> g(n);
	for (int i = 0; i < m; ++i) {
		int x, y, w;
		cin >> x >> y >> w; x--, y--;
		g[x].emplace_back(y, w);
		g[y].emplace_back(x, w);
	}
	vector<int> dS = run_dijkstra(n, g, S);
	vector<int> dT = run_dijkstra(n, g, T);
	vector<int> dX = run_dijkstra(n, g, X);
	vector<int> dY = run_dijkstra(n, g, Y);
	long long min_dist = dS[T];
	auto Calc = [&](const vector<int>& s, const vector<int>& t, const vector<int>& d, int start) {
		vector<int> topo;
		vector<bool> vis(n, false);
		function<void(int)> dfs = [&](int u) {
			vis[u] = true;
			for (auto& p : g[u]) {
				int v = p.first;
				int w = p.second;
				if (s[u] + w == min_dist - t[v] && !vis[v]) {
					dfs(v);
				}
			}
			topo.push_back(u);
		};
		dfs(start);
		reverse(ALL(topo));
		vector<int> dp(n, LLONG_MAX / 2);
		for (int u : topo) {
			dp[u] = min(dp[u], d[u]);
			for (auto& p : g[u]) {
				int v = p.first;
				int w = p.second;
				if (s[u] + w == min_dist - t[v]) {
					dp[v] = min(dp[v], dp[u]);
				}
			}
		}
		return dp;
	};
	vector<int> sx = Calc(dS, dT, dX, S);
	vector<int> sy = Calc(dS, dT, dY, S);
	vector<int> tx = Calc(dT, dS, dX, T);
	vector<int> ty = Calc(dT, dS, dY, T);
	int ans = dX[Y];
	for (int i = 0; i < n; ++i) {
		ans = min(ans, min(sx[i] + ty[i], sy[i] + tx[i]));
	}
	cout << ans << '\n';

#ifdef LOCAL
	cout << '\n' << clock() << "ms.";
#endif // LOCAL
	return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 19296 KB Output is correct
2 Correct 288 ms 19952 KB Output is correct
3 Correct 311 ms 25184 KB Output is correct
4 Correct 171 ms 19364 KB Output is correct
5 Correct 221 ms 20336 KB Output is correct
6 Correct 194 ms 19360 KB Output is correct
7 Correct 274 ms 20564 KB Output is correct
8 Correct 258 ms 20736 KB Output is correct
9 Correct 174 ms 19288 KB Output is correct
10 Correct 132 ms 19344 KB Output is correct
11 Correct 94 ms 18464 KB Output is correct
12 Correct 182 ms 19224 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 21992 KB Output is correct
2 Correct 217 ms 22516 KB Output is correct
3 Correct 239 ms 22008 KB Output is correct
4 Correct 214 ms 22252 KB Output is correct
5 Correct 271 ms 23464 KB Output is correct
6 Correct 284 ms 24972 KB Output is correct
7 Correct 279 ms 25296 KB Output is correct
8 Correct 260 ms 22240 KB Output is correct
9 Correct 295 ms 23000 KB Output is correct
10 Correct 235 ms 22028 KB Output is correct
11 Correct 101 ms 20036 KB Output is correct
12 Correct 249 ms 25244 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1628 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 10 ms 3176 KB Output is correct
5 Correct 8 ms 2136 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 5 ms 1624 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 19296 KB Output is correct
2 Correct 288 ms 19952 KB Output is correct
3 Correct 311 ms 25184 KB Output is correct
4 Correct 171 ms 19364 KB Output is correct
5 Correct 221 ms 20336 KB Output is correct
6 Correct 194 ms 19360 KB Output is correct
7 Correct 274 ms 20564 KB Output is correct
8 Correct 258 ms 20736 KB Output is correct
9 Correct 174 ms 19288 KB Output is correct
10 Correct 132 ms 19344 KB Output is correct
11 Correct 94 ms 18464 KB Output is correct
12 Correct 182 ms 19224 KB Output is correct
13 Correct 246 ms 21992 KB Output is correct
14 Correct 217 ms 22516 KB Output is correct
15 Correct 239 ms 22008 KB Output is correct
16 Correct 214 ms 22252 KB Output is correct
17 Correct 271 ms 23464 KB Output is correct
18 Correct 284 ms 24972 KB Output is correct
19 Correct 279 ms 25296 KB Output is correct
20 Correct 260 ms 22240 KB Output is correct
21 Correct 295 ms 23000 KB Output is correct
22 Correct 235 ms 22028 KB Output is correct
23 Correct 101 ms 20036 KB Output is correct
24 Correct 249 ms 25244 KB Output is correct
25 Correct 6 ms 1628 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 10 ms 3176 KB Output is correct
29 Correct 8 ms 2136 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 5 ms 1624 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 185 ms 18912 KB Output is correct
41 Correct 190 ms 19432 KB Output is correct
42 Correct 192 ms 19392 KB Output is correct
43 Correct 125 ms 19208 KB Output is correct
44 Correct 114 ms 19156 KB Output is correct
45 Correct 246 ms 20284 KB Output is correct
46 Correct 263 ms 20492 KB Output is correct
47 Correct 191 ms 19396 KB Output is correct
48 Correct 149 ms 16624 KB Output is correct
49 Correct 151 ms 18916 KB Output is correct
50 Correct 258 ms 20404 KB Output is correct
51 Correct 244 ms 20508 KB Output is correct