oj.uz

Submission #959084

# Submission time Handle Problem Language Result Execution time Memory
959084 2024-04-07T13:15:54 Z liaochengle Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 439 ms 32888 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<pair<ll, ll>> graph[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;
bool visited[100001];

void dijkstra1(ll start, ll arr[]) {
	fill(visited, visited + 100001, false);

	priority_queue<pair<ll, ll>> pq;
	pq.push({0, start});
	while (!pq.empty()) {
		ll c, node;
		tie(c, node) = pq.top();
		pq.pop();

		if (!visited[node]) {
			arr[node] = -c;
			visited[node] = true;
			for (auto &i : graph[node]) pq.push({c - i.second, i.first});
		}
	}
}

void dijkstra2(ll start, ll end) {
	fill(dp[0], dp[0] + 100001, LLONG_MAX / 2);
	fill(dp[1], dp[1] + 100001, LLONG_MAX / 2);
	fill(visited, visited + 100001, false);

	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push({0, {start, 0}});
	dp[0][0] = dp[1][0] = LLONG_MAX / 2;
	while (!pq.empty()) {
		ll c, node, par;
		pair<ll, ll> p;
		tie(c, p) = pq.top();
		tie(node, par) = p;
		pq.pop();

		if (!visited[node]) {
			visited[node] = true;
			ds[node] = -c;
			dp[0][node] = min(du[node], dp[0][par]);
			dp[1][node] = min(dv[node], dp[1][par]);
			for (auto i : graph[node]) pq.push({c - i.second, {i.first, node}});
		} else if (-c == ds[node]) {
			if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <=
			    dp[0][node] + dp[1][node]) {
				dp[0][node] = min(du[node], dp[0][par]);
				dp[1][node] = min(dv[node], dp[1][par]);
			}
		}
	}

	ans = min(ans, dp[0][end] + dp[1][end]);
}

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	ll n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 0; i < m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}

	dijkstra1(u, du);
	dijkstra1(v, dv);

	ans = du[v];

	dijkstra2(s, t);
	dijkstra2(t, s);

	cout << ans << '\n';
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 27940 KB Output is correct
2 Correct 368 ms 27488 KB Output is correct
3 Correct 363 ms 26916 KB Output is correct
4 Correct 416 ms 31288 KB Output is correct
5 Correct 325 ms 26744 KB Output is correct
6 Correct 409 ms 31540 KB Output is correct
7 Correct 383 ms 31124 KB Output is correct
8 Correct 399 ms 32216 KB Output is correct
9 Correct 403 ms 32216 KB Output is correct
10 Correct 386 ms 32128 KB Output is correct
11 Correct 96 ms 13896 KB Output is correct
12 Correct 428 ms 32880 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 28300 KB Output is correct
2 Correct 336 ms 26816 KB Output is correct
3 Correct 384 ms 31144 KB Output is correct
4 Correct 408 ms 26560 KB Output is correct
5 Correct 358 ms 26684 KB Output is correct
6 Correct 406 ms 30492 KB Output is correct
7 Correct 416 ms 26548 KB Output is correct
8 Correct 377 ms 26548 KB Output is correct
9 Correct 394 ms 26352 KB Output is correct
10 Correct 379 ms 31212 KB Output is correct
11 Correct 93 ms 14016 KB Output is correct
12 Correct 405 ms 30272 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9452 KB Output is correct
2 Correct 2 ms 6648 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 64 ms 12940 KB Output is correct
5 Correct 33 ms 10876 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 4 ms 7004 KB Output is correct
8 Correct 5 ms 7200 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 34 ms 10888 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 3 ms 6912 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 27940 KB Output is correct
2 Correct 368 ms 27488 KB Output is correct
3 Correct 363 ms 26916 KB Output is correct
4 Correct 416 ms 31288 KB Output is correct
5 Correct 325 ms 26744 KB Output is correct
6 Correct 409 ms 31540 KB Output is correct
7 Correct 383 ms 31124 KB Output is correct
8 Correct 399 ms 32216 KB Output is correct
9 Correct 403 ms 32216 KB Output is correct
10 Correct 386 ms 32128 KB Output is correct
11 Correct 96 ms 13896 KB Output is correct
12 Correct 428 ms 32880 KB Output is correct
13 Correct 397 ms 28300 KB Output is correct
14 Correct 336 ms 26816 KB Output is correct
15 Correct 384 ms 31144 KB Output is correct
16 Correct 408 ms 26560 KB Output is correct
17 Correct 358 ms 26684 KB Output is correct
18 Correct 406 ms 30492 KB Output is correct
19 Correct 416 ms 26548 KB Output is correct
20 Correct 377 ms 26548 KB Output is correct
21 Correct 394 ms 26352 KB Output is correct
22 Correct 379 ms 31212 KB Output is correct
23 Correct 93 ms 14016 KB Output is correct
24 Correct 405 ms 30272 KB Output is correct
25 Correct 30 ms 9452 KB Output is correct
26 Correct 2 ms 6648 KB Output is correct
27 Correct 3 ms 6748 KB Output is correct
28 Correct 64 ms 12940 KB Output is correct
29 Correct 33 ms 10876 KB Output is correct
30 Correct 3 ms 7004 KB Output is correct
31 Correct 4 ms 7004 KB Output is correct
32 Correct 5 ms 7200 KB Output is correct
33 Correct 3 ms 7004 KB Output is correct
34 Correct 34 ms 10888 KB Output is correct
35 Correct 2 ms 6748 KB Output is correct
36 Correct 2 ms 6748 KB Output is correct
37 Correct 2 ms 6748 KB Output is correct
38 Correct 3 ms 6912 KB Output is correct
39 Correct 3 ms 6748 KB Output is correct
40 Correct 439 ms 32776 KB Output is correct
41 Correct 420 ms 32780 KB Output is correct
42 Correct 428 ms 32888 KB Output is correct
43 Correct 100 ms 14068 KB Output is correct
44 Correct 108 ms 13968 KB Output is correct
45 Correct 378 ms 25400 KB Output is correct
46 Correct 390 ms 26388 KB Output is correct
47 Correct 431 ms 26824 KB Output is correct
48 Correct 104 ms 13596 KB Output is correct
49 Correct 425 ms 30948 KB Output is correct
50 Correct 379 ms 26248 KB Output is correct
51 Correct 332 ms 25232 KB Output is correct