oj.uz

Submission #97834

# Submission time Handle Problem Language Result Execution time Memory
97834 2019-02-18T18:51:41 Z Anai Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 442 ms 21648 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

const int N = 1e5 + 5;

vector<pii> g[N];
vector<int> dag[N];
i64 dist[N], dist_fst[N], dist_snd[N], dp[N][4];
int reach[N], in_deg[N];

vector<int> topsort;
int n, m, src, snk, fst, snd;


static void dijkstra(int nod, i64 dist[N]) {
	priority_queue<pll> pq;

	memset(dist, 0x3f, N * sizeof(i64));
	dist[nod] = 0;
	pq.emplace(dist[nod], nod);

	while (!pq.empty()) {
		i64 dst = -pq.top().x;
		int u = pq.top().y;

		pq.pop();
		if (dst != dist[u])
			continue;

		for (auto v: g[u]) if (dist[v.x] > dst + v.y) {
			dist[v.x] = dst + v.y;
			pq.emplace(-dist[v.x], v.x); } } }

static void get_dp() {
	vector<int> srt(n);


	iota(begin(srt), end(srt), 1);
	sort(begin(srt), end(srt), [&](const int &a, const int &b) {
		return dist[a] > dist[b]; });

	memset(dp, 0x3f, sizeof dp);
	dp[snk][0] = 0;
	dp[snk][1] = dist_fst[snk];
	dp[snk][2] = dist_snd[snk];
	dp[snk][3] = dist_fst[snk] + dist_snd[snk];

	for (auto u: srt) {
		for (auto e: g[u]) if (dist[u] + e.y == dist[e.x]) {
			int v = e.x;
			dp[u][0] = min(dp[u][0], dp[v][0]);

			dp[u][1] = min(dp[u][1], dp[v][0] + dist_fst[u]);
			dp[u][1] = min(dp[u][1], dp[v][1]);

			dp[u][2] = min(dp[u][2], dp[v][0] + dist_snd[u]);
			dp[u][2] = min(dp[u][2], dp[v][2]);

			dp[u][3] = min(dp[u][3], dp[v][0] + dist_fst[u] + dist_snd[u]);
			dp[u][3] = min(dp[u][3], dp[v][1] + dist_snd[u]);
			dp[u][3] = min(dp[u][3], dp[v][2] + dist_fst[u]);
			dp[u][3] = min(dp[u][3], dp[v][3]); } } }

int main() {
#ifdef HOME
	freopen("joi_commuter.in", "r", stdin);
	freopen("joi_commuter.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> src >> snk;
	cin >> fst >> snd;

	for (int u, v, c, i = 0; i < m; ++i) {
		cin >> u >> v >> c;
		g[u].emplace_back(v, c);
		g[v].emplace_back(u, c); }

	dijkstra(src, dist);
	dijkstra(fst, dist_fst);
	dijkstra(snd, dist_snd);
	get_dp();

	cout << min(dist_fst[snd], dp[src][3]) << '\n';

	return 0; }

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 17376 KB Output is correct
2 Correct 377 ms 17136 KB Output is correct
3 Correct 370 ms 17392 KB Output is correct
4 Correct 414 ms 17140 KB Output is correct
5 Correct 354 ms 17256 KB Output is correct
6 Correct 439 ms 17168 KB Output is correct
7 Correct 365 ms 17288 KB Output is correct
8 Correct 399 ms 17148 KB Output is correct
9 Correct 389 ms 17560 KB Output is correct
10 Correct 404 ms 17108 KB Output is correct
11 Correct 204 ms 14084 KB Output is correct
12 Correct 403 ms 17320 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 17256 KB Output is correct
2 Correct 408 ms 17400 KB Output is correct
3 Correct 407 ms 17264 KB Output is correct
4 Correct 367 ms 17268 KB Output is correct
5 Correct 422 ms 17236 KB Output is correct
6 Correct 385 ms 17132 KB Output is correct
7 Correct 382 ms 17244 KB Output is correct
8 Correct 389 ms 17464 KB Output is correct
9 Correct 401 ms 17160 KB Output is correct
10 Correct 442 ms 17356 KB Output is correct
11 Correct 171 ms 14252 KB Output is correct
12 Correct 394 ms 17236 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11264 KB Output is correct
2 Correct 11 ms 10624 KB Output is correct
3 Correct 12 ms 10624 KB Output is correct
4 Correct 26 ms 12672 KB Output is correct
5 Correct 21 ms 11520 KB Output is correct
6 Correct 11 ms 10624 KB Output is correct
7 Correct 13 ms 10624 KB Output is correct
8 Correct 13 ms 10624 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 22 ms 11648 KB Output is correct
11 Correct 12 ms 10496 KB Output is correct
12 Correct 12 ms 10496 KB Output is correct
13 Correct 12 ms 10496 KB Output is correct
14 Correct 11 ms 10624 KB Output is correct
15 Correct 11 ms 10624 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 17376 KB Output is correct
2 Correct 377 ms 17136 KB Output is correct
3 Correct 370 ms 17392 KB Output is correct
4 Correct 414 ms 17140 KB Output is correct
5 Correct 354 ms 17256 KB Output is correct
6 Correct 439 ms 17168 KB Output is correct
7 Correct 365 ms 17288 KB Output is correct
8 Correct 399 ms 17148 KB Output is correct
9 Correct 389 ms 17560 KB Output is correct
10 Correct 404 ms 17108 KB Output is correct
11 Correct 204 ms 14084 KB Output is correct
12 Correct 403 ms 17320 KB Output is correct
13 Correct 395 ms 17256 KB Output is correct
14 Correct 408 ms 17400 KB Output is correct
15 Correct 407 ms 17264 KB Output is correct
16 Correct 367 ms 17268 KB Output is correct
17 Correct 422 ms 17236 KB Output is correct
18 Correct 385 ms 17132 KB Output is correct
19 Correct 382 ms 17244 KB Output is correct
20 Correct 389 ms 17464 KB Output is correct
21 Correct 401 ms 17160 KB Output is correct
22 Correct 442 ms 17356 KB Output is correct
23 Correct 171 ms 14252 KB Output is correct
24 Correct 394 ms 17236 KB Output is correct
25 Correct 18 ms 11264 KB Output is correct
26 Correct 11 ms 10624 KB Output is correct
27 Correct 12 ms 10624 KB Output is correct
28 Correct 26 ms 12672 KB Output is correct
29 Correct 21 ms 11520 KB Output is correct
30 Correct 11 ms 10624 KB Output is correct
31 Correct 13 ms 10624 KB Output is correct
32 Correct 13 ms 10624 KB Output is correct
33 Correct 13 ms 10624 KB Output is correct
34 Correct 22 ms 11648 KB Output is correct
35 Correct 12 ms 10496 KB Output is correct
36 Correct 12 ms 10496 KB Output is correct
37 Correct 12 ms 10496 KB Output is correct
38 Correct 11 ms 10624 KB Output is correct
39 Correct 11 ms 10624 KB Output is correct
40 Correct 350 ms 21028 KB Output is correct
41 Correct 427 ms 21648 KB Output is correct
42 Correct 383 ms 21600 KB Output is correct
43 Correct 182 ms 16376 KB Output is correct
44 Correct 174 ms 16120 KB Output is correct
45 Correct 414 ms 21224 KB Output is correct
46 Correct 356 ms 20536 KB Output is correct
47 Correct 370 ms 21084 KB Output is correct
48 Correct 212 ms 15608 KB Output is correct
49 Correct 380 ms 20788 KB Output is correct
50 Correct 408 ms 20716 KB Output is correct
51 Correct 366 ms 20736 KB Output is correct