oj.uz

Submission #347936

# Submission time Handle Problem Language Result Execution time Memory
347936 2021-01-13T20:38:32 Z TruaShamu Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 626 ms 27384 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 610 ms 27344 KB Output is correct
2 Correct 545 ms 26816 KB Output is correct
3 Correct 559 ms 26308 KB Output is correct
4 Correct 613 ms 26352 KB Output is correct
5 Correct 542 ms 23092 KB Output is correct
6 Correct 626 ms 27252 KB Output is correct
7 Correct 544 ms 26672 KB Output is correct
8 Correct 544 ms 26876 KB Output is correct
9 Correct 609 ms 27308 KB Output is correct
10 Correct 591 ms 27240 KB Output is correct
11 Correct 157 ms 12012 KB Output is correct
12 Correct 613 ms 27384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 27068 KB Output is correct
2 Correct 530 ms 23272 KB Output is correct
3 Correct 543 ms 26568 KB Output is correct
4 Correct 541 ms 23328 KB Output is correct
5 Correct 534 ms 23004 KB Output is correct
6 Correct 540 ms 26300 KB Output is correct
7 Correct 526 ms 23020 KB Output is correct
8 Correct 531 ms 23176 KB Output is correct
9 Correct 529 ms 23056 KB Output is correct
10 Correct 536 ms 26512 KB Output is correct
11 Correct 155 ms 12012 KB Output is correct
12 Correct 552 ms 26408 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7164 KB Output is correct
2 Correct 4 ms 4460 KB Output is correct
3 Correct 4 ms 4460 KB Output is correct
4 Correct 88 ms 9892 KB Output is correct
5 Correct 44 ms 8108 KB Output is correct
6 Correct 7 ms 4588 KB Output is correct
7 Correct 7 ms 4692 KB Output is correct
8 Correct 8 ms 4788 KB Output is correct
9 Correct 6 ms 4588 KB Output is correct
10 Correct 42 ms 8088 KB Output is correct
11 Correct 3 ms 4332 KB Output is correct
12 Correct 4 ms 4480 KB Output is correct
13 Correct 4 ms 4460 KB Output is correct
14 Correct 5 ms 4460 KB Output is correct
15 Correct 5 ms 4480 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 27344 KB Output is correct
2 Correct 545 ms 26816 KB Output is correct
3 Correct 559 ms 26308 KB Output is correct
4 Correct 613 ms 26352 KB Output is correct
5 Correct 542 ms 23092 KB Output is correct
6 Correct 626 ms 27252 KB Output is correct
7 Correct 544 ms 26672 KB Output is correct
8 Correct 544 ms 26876 KB Output is correct
9 Correct 609 ms 27308 KB Output is correct
10 Correct 591 ms 27240 KB Output is correct
11 Correct 157 ms 12012 KB Output is correct
12 Correct 613 ms 27384 KB Output is correct
13 Correct 588 ms 27068 KB Output is correct
14 Correct 530 ms 23272 KB Output is correct
15 Correct 543 ms 26568 KB Output is correct
16 Correct 541 ms 23328 KB Output is correct
17 Correct 534 ms 23004 KB Output is correct
18 Correct 540 ms 26300 KB Output is correct
19 Correct 526 ms 23020 KB Output is correct
20 Correct 531 ms 23176 KB Output is correct
21 Correct 529 ms 23056 KB Output is correct
22 Correct 536 ms 26512 KB Output is correct
23 Correct 155 ms 12012 KB Output is correct
24 Correct 552 ms 26408 KB Output is correct
25 Correct 43 ms 7164 KB Output is correct
26 Correct 4 ms 4460 KB Output is correct
27 Correct 4 ms 4460 KB Output is correct
28 Correct 88 ms 9892 KB Output is correct
29 Correct 44 ms 8108 KB Output is correct
30 Correct 7 ms 4588 KB Output is correct
31 Correct 7 ms 4692 KB Output is correct
32 Correct 8 ms 4788 KB Output is correct
33 Correct 6 ms 4588 KB Output is correct
34 Correct 42 ms 8088 KB Output is correct
35 Correct 3 ms 4332 KB Output is correct
36 Correct 4 ms 4480 KB Output is correct
37 Correct 4 ms 4460 KB Output is correct
38 Correct 5 ms 4460 KB Output is correct
39 Correct 5 ms 4480 KB Output is correct
40 Correct 598 ms 26832 KB Output is correct
41 Correct 619 ms 27144 KB Output is correct
42 Correct 615 ms 27096 KB Output is correct
43 Correct 166 ms 12012 KB Output is correct
44 Correct 166 ms 12012 KB Output is correct
45 Correct 546 ms 21908 KB Output is correct
46 Correct 551 ms 21788 KB Output is correct
47 Correct 610 ms 23052 KB Output is correct
48 Correct 174 ms 12012 KB Output is correct
49 Correct 607 ms 25728 KB Output is correct
50 Correct 545 ms 21928 KB Output is correct
51 Correct 545 ms 21720 KB Output is correct