oj.uz

Submission #575200

# Submission time Handle Problem Language Result Execution time Memory
575200 2022-06-09T22:21:06 Z four_specks Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 439 ms 43508 KB 
#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve()
{
    int n, m;
    cin >> n >> m;

    int s, t, u, v;
    cin >> s >> t >> u >> v, --s, --t, --u, --v;

    vector<vector<pair<int, long>>> adj(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        long c;
        cin >> a >> b >> c, --a, --b;

        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    vector<vector<int>> gr_fw(n), gr_bk(n);
    {
        vector<long> dist(n, LONG_MAX);
        priority_queue<pair<long, int>> pq;
        vector<vector<int>> gr1(n);
        vector<vector<int>> todo(n);
        dist[s] = 0;
        for (pq.emplace(-dist[s], s); !pq.empty();)
        {
            auto [d, a] = pq.top();
            pq.pop();

            if (d != -dist[a])
                continue;

            for (int b : todo[a])
                gr1[a].push_back(b);

            for (auto [b, c] : adj[a])
            {
                if (dist[a] + c < dist[b])
                {
                    todo[b].clear(),
                    todo[b].push_back(a);

                    dist[b] = dist[a] + c;
                    pq.emplace(-dist[b], b);
                }
                else if (dist[a] + c == dist[b])
                    todo[b].push_back(a);
            }
        }

        queue<int> q;
        vector<bool> done(n, 0);
        for (q.push(t); !q.empty();)
        {
            int a = q.front();
            q.pop();

            if (done[a])
                continue;

            done[a] = 1;

            for (int b : gr1[a])
            {
                gr_fw[b].push_back(a), gr_bk[a].push_back(b);
                q.push(b);
            }
        }
    }
    long res = LONG_MAX;
    {
        vector<long> dist_u(n, LONG_MAX), dist_v(n, LONG_MAX);
        {
            priority_queue<pair<long, int>> pq;
            dist_u[u] = 0;
            for (pq.emplace(-dist_u[u], u); !pq.empty();)
            {
                auto [d, a] = pq.top();
                pq.pop();

                if (d != -dist_u[a])
                    continue;

                for (auto [b, c] : adj[a])
                {
                    if (dist_u[a] + c < dist_u[b])
                    {
                        dist_u[b] = dist_u[a] + c;
                        pq.emplace(-dist_u[b], b);
                    }
                }
            }
        }
        {
            priority_queue<pair<long, int>> pq;
            dist_v[v] = 0;
            for (pq.emplace(-dist_v[v], v); !pq.empty();)
            {
                auto [d, a] = pq.top();
                pq.pop();

                if (d != -dist_v[a])
                    continue;

                for (auto [b, c] : adj[a])
                {
                    if (dist_v[a] + c < dist_v[b])
                    {
                        dist_v[b] = dist_v[a] + c;
                        pq.emplace(-dist_v[b], b);
                    }
                }
            }
        }

        res = dist_u[v];

        for (auto [gr, k] : {pair(gr_fw, s), pair(gr_bk, t)})
        {
            vector<int> deg(n);
            for (int i = 0; i < n; i++)
            {
                for (int j : gr[i])
                    deg[j]++;
            }

            queue<int> q;
            vector<long> dp_u = dist_u, dp_v = dist_v;
            for (q.push(k); !q.empty();)
            {
                int a = q.front();
                q.pop();

                // cerr << a << ' ' << dp_u[a] << ' ' << dp_v[a] << '\n';
                res = min(res, dp_u[a] + dp_v[a]);

                for (int b : gr[a])
                {
                    dp_u[b] = min(dist_u[b], dp_u[a]),
                    dp_v[b] = min(dist_v[b], dp_v[a]);
                    if (--deg[b] == 0)
                        q.push(b);
                }
            }
        }
    }

    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 30252 KB Output is correct
2 Correct 308 ms 33040 KB Output is correct
3 Correct 360 ms 37968 KB Output is correct
4 Correct 303 ms 31880 KB Output is correct
5 Correct 345 ms 35808 KB Output is correct
6 Correct 290 ms 30228 KB Output is correct
7 Correct 382 ms 37296 KB Output is correct
8 Correct 347 ms 36040 KB Output is correct
9 Correct 291 ms 31120 KB Output is correct
10 Correct 276 ms 30420 KB Output is correct
11 Correct 197 ms 29808 KB Output is correct
12 Correct 320 ms 30328 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 32780 KB Output is correct
2 Correct 362 ms 33068 KB Output is correct
3 Correct 320 ms 31672 KB Output is correct
4 Correct 316 ms 33052 KB Output is correct
5 Correct 319 ms 33416 KB Output is correct
6 Correct 330 ms 36964 KB Output is correct
7 Correct 382 ms 38044 KB Output is correct
8 Correct 352 ms 32528 KB Output is correct
9 Correct 352 ms 33464 KB Output is correct
10 Correct 357 ms 32168 KB Output is correct
11 Correct 223 ms 32660 KB Output is correct
12 Correct 357 ms 37620 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1876 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 14 ms 3116 KB Output is correct
5 Correct 6 ms 1620 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6 ms 1612 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 30252 KB Output is correct
2 Correct 308 ms 33040 KB Output is correct
3 Correct 360 ms 37968 KB Output is correct
4 Correct 303 ms 31880 KB Output is correct
5 Correct 345 ms 35808 KB Output is correct
6 Correct 290 ms 30228 KB Output is correct
7 Correct 382 ms 37296 KB Output is correct
8 Correct 347 ms 36040 KB Output is correct
9 Correct 291 ms 31120 KB Output is correct
10 Correct 276 ms 30420 KB Output is correct
11 Correct 197 ms 29808 KB Output is correct
12 Correct 320 ms 30328 KB Output is correct
13 Correct 340 ms 32780 KB Output is correct
14 Correct 362 ms 33068 KB Output is correct
15 Correct 320 ms 31672 KB Output is correct
16 Correct 316 ms 33052 KB Output is correct
17 Correct 319 ms 33416 KB Output is correct
18 Correct 330 ms 36964 KB Output is correct
19 Correct 382 ms 38044 KB Output is correct
20 Correct 352 ms 32528 KB Output is correct
21 Correct 352 ms 33464 KB Output is correct
22 Correct 357 ms 32168 KB Output is correct
23 Correct 223 ms 32660 KB Output is correct
24 Correct 357 ms 37620 KB Output is correct
25 Correct 7 ms 1876 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 14 ms 3116 KB Output is correct
29 Correct 6 ms 1620 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 6 ms 1612 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 256 ms 29604 KB Output is correct
41 Correct 295 ms 29652 KB Output is correct
42 Correct 299 ms 30360 KB Output is correct
43 Correct 226 ms 38512 KB Output is correct
44 Correct 219 ms 38508 KB Output is correct
45 Correct 435 ms 43352 KB Output is correct
46 Correct 403 ms 43508 KB Output is correct
47 Correct 325 ms 31100 KB Output is correct
48 Correct 229 ms 38504 KB Output is correct
49 Correct 262 ms 31264 KB Output is correct
50 Correct 360 ms 40016 KB Output is correct
51 Correct 439 ms 43416 KB Output is correct