oj.uz

Submission #448373

# Submission time Handle Problem Language Result Execution time Memory
448373 2021-07-29T22:22:34 Z training4usaco Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 620 ms 31396 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
 
#define MAXN 100001
#define INF 4600000000000000000

ll n, m, s, t, u, v;
vector<vector<pll>> adj(MAXN);
vector<ll> distu(MAXN), distv(MAXN), dists(MAXN);
vector<vector<ll>> dp(2, vector<ll>(MAXN));
ll answer;
vector<bool> visited(MAXN, false);
 
void dijkstra1(ll start, vector<ll>& dist) {
	visited = vector<bool>(MAXN, false);
 
	priority_queue<pll, vector<pll>, greater<pll>> pq;

	pq.push({0, start});
	while (!pq.empty()) {
		ll cdist = pq.top().first;
		ll node = pq.top().second;
		pq.pop();
 
		if (!visited[node]) {
			dist[node] = cdist;
			visited[node] = true;
			for (auto i : adj[node]) {
                pq.push({cdist + i.second, i.first});
            }
		}
	}
}
 
void dijkstra2(ll start, ll end) {
    dp[0] = vector<ll>(MAXN, INF);
    dp[1] = vector<ll>(MAXN, INF);
	visited = vector<bool>(MAXN, false);
 
	priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
	pq.push({0, {start, 0}});

    dp[0][0] = INF;
    dp[1][0] = INF;
	while (!pq.empty()) {
		ll cdist = pq.top().first;
        ll node = pq.top().second.first;
        ll par = pq.top().second.second;
		pq.pop();
 
		if (!visited[node]) {
			visited[node] = true;
			dists[node] = cdist;
			dp[0][node] = min(distu[node], dp[0][par]);
			dp[1][node] = min(distv[node], dp[1][par]);

			for (auto i : adj[node]) {
                pq.push({cdist + i.second, {i.first, node}});
            }
		} 
        else if (cdist == dists[node]) {
			if (min(distu[node], dp[0][par]) + min(distv[node], dp[1][par]) <= dp[0][node] + dp[1][node]) {
				dp[0][node] = min(distu[node], dp[0][par]);
				dp[1][node] = min(distv[node], dp[1][par]);
			}
		}
	}
 
	answer = min(answer, dp[0][end] + dp[1][end]);
}
 
int main() {
	cin >> n >> m >> s >> t >> u >> v;

	for (int i = 0; i < m; i++) {
		ll a, b, cdist;
		cin >> a >> b >> cdist;
		adj[a].push_back({b, cdist});
		adj[b].push_back({a, cdist});
	}
 
	dijkstra1(u, distu);
	dijkstra1(v, distv);
 
	answer = distu[v];
 
	dijkstra2(s, t);
 
	cout << answer << endl;
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 31028 KB Output is correct
2 Correct 518 ms 29976 KB Output is correct
3 Correct 546 ms 26176 KB Output is correct
4 Correct 620 ms 30000 KB Output is correct
5 Correct 504 ms 25672 KB Output is correct
6 Correct 577 ms 30808 KB Output is correct
7 Correct 514 ms 29820 KB Output is correct
8 Correct 518 ms 29656 KB Output is correct
9 Correct 586 ms 31336 KB Output is correct
10 Correct 586 ms 31396 KB Output is correct
11 Correct 182 ms 14516 KB Output is correct
12 Correct 569 ms 31364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 30000 KB Output is correct
2 Correct 509 ms 26168 KB Output is correct
3 Correct 510 ms 26660 KB Output is correct
4 Correct 521 ms 26132 KB Output is correct
5 Correct 512 ms 26180 KB Output is correct
6 Correct 517 ms 26440 KB Output is correct
7 Correct 508 ms 26536 KB Output is correct
8 Correct 512 ms 26036 KB Output is correct
9 Correct 519 ms 26780 KB Output is correct
10 Correct 510 ms 26084 KB Output is correct
11 Correct 226 ms 14640 KB Output is correct
12 Correct 519 ms 26272 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9796 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 5 ms 7356 KB Output is correct
4 Correct 93 ms 12800 KB Output is correct
5 Correct 48 ms 10676 KB Output is correct
6 Correct 7 ms 7484 KB Output is correct
7 Correct 9 ms 7484 KB Output is correct
8 Correct 10 ms 7612 KB Output is correct
9 Correct 7 ms 7612 KB Output is correct
10 Correct 50 ms 9832 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Correct 5 ms 7356 KB Output is correct
13 Correct 6 ms 7372 KB Output is correct
14 Correct 6 ms 7452 KB Output is correct
15 Correct 6 ms 7356 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 31028 KB Output is correct
2 Correct 518 ms 29976 KB Output is correct
3 Correct 546 ms 26176 KB Output is correct
4 Correct 620 ms 30000 KB Output is correct
5 Correct 504 ms 25672 KB Output is correct
6 Correct 577 ms 30808 KB Output is correct
7 Correct 514 ms 29820 KB Output is correct
8 Correct 518 ms 29656 KB Output is correct
9 Correct 586 ms 31336 KB Output is correct
10 Correct 586 ms 31396 KB Output is correct
11 Correct 182 ms 14516 KB Output is correct
12 Correct 569 ms 31364 KB Output is correct
13 Correct 553 ms 30000 KB Output is correct
14 Correct 509 ms 26168 KB Output is correct
15 Correct 510 ms 26660 KB Output is correct
16 Correct 521 ms 26132 KB Output is correct
17 Correct 512 ms 26180 KB Output is correct
18 Correct 517 ms 26440 KB Output is correct
19 Correct 508 ms 26536 KB Output is correct
20 Correct 512 ms 26036 KB Output is correct
21 Correct 519 ms 26780 KB Output is correct
22 Correct 510 ms 26084 KB Output is correct
23 Correct 226 ms 14640 KB Output is correct
24 Correct 519 ms 26272 KB Output is correct
25 Correct 50 ms 9796 KB Output is correct
26 Correct 5 ms 7356 KB Output is correct
27 Correct 5 ms 7356 KB Output is correct
28 Correct 93 ms 12800 KB Output is correct
29 Correct 48 ms 10676 KB Output is correct
30 Correct 7 ms 7484 KB Output is correct
31 Correct 9 ms 7484 KB Output is correct
32 Correct 10 ms 7612 KB Output is correct
33 Correct 7 ms 7612 KB Output is correct
34 Correct 50 ms 9832 KB Output is correct
35 Correct 5 ms 7372 KB Output is correct
36 Correct 5 ms 7356 KB Output is correct
37 Correct 6 ms 7372 KB Output is correct
38 Correct 6 ms 7452 KB Output is correct
39 Correct 6 ms 7356 KB Output is correct
40 Correct 577 ms 30812 KB Output is correct
41 Correct 587 ms 31292 KB Output is correct
42 Correct 577 ms 31348 KB Output is correct
43 Correct 189 ms 14756 KB Output is correct
44 Correct 191 ms 14592 KB Output is correct
45 Correct 511 ms 25024 KB Output is correct
46 Correct 515 ms 24764 KB Output is correct
47 Correct 565 ms 26444 KB Output is correct
48 Correct 177 ms 14072 KB Output is correct
49 Correct 558 ms 29312 KB Output is correct
50 Correct 508 ms 25076 KB Output is correct
51 Correct 507 ms 25172 KB Output is correct