oj.uz

Submission #159920

# Submission time Handle Problem Language Result Execution time Memory
159920 2019-10-25T12:05:42 Z XCoder Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 765 ms 18164 KB 
#include <bits/stdc++.h>

#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define REP(i,n)   FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back
#define ITER(v) __typeof((v).begin())
#define FOREACH(i,v) for(ITER(v) i=(v).begin();i!=(v).end();i++)

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;
typedef map<int,int> mii;
typedef vector<int> vi;

const LL INF = 1LL << 60;
using Graph = vector<vector<pii>>;
using Dist = vector<LL>;
using Node = tuple<LL, int>;  // <cost, node_id>

int N, M, S, T, U, V;
Graph G;

Dist compute_shortest_path(Graph &G, vector<int> src_nodes, int N) {
    Dist D(N + 1, INF);
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    for (auto &src : src_nodes) {
        D[src] = 0LL;
        pq.push({D[src], src});
    }

    while (!pq.empty()) {
        LL cur;
        int x;
        tie(cur, x) = pq.top();
        pq.pop();

        if (D[x] > cur) continue;

        for (auto &it : G[x]) {
            LL cost;
            int y;
            tie(y, cost) = it;
            if (cur + cost < D[y]) {
                D[y] = cur + cost;    
                pq.push({D[y], y});
            }
        }
    }
    return D;
}


Dist S_dist, T_dist, U_dist, V_dist;
LL ST_shortest_path_cost;
Graph G_ST; // edges consisting of edges used in any shortest paths


void dfs_2(int x, Dist &u_min_dist, Dist &U_dist) {
    // Already tried
    if (u_min_dist[x] != INF) return;

    // DFS - traverse all possible shortest paths
    // x : current node
    // V ~~> some node visited before -> x ~~> U

    u_min_dist[x] = U_dist[x];
    for (auto &edge : G[x]) {
        int y, cost;
        tie(y, cost) = edge;
        // S -> x -> y -> T is a possible S-T shortest path
        if (S_dist[x] + cost + T_dist[y] == ST_shortest_path_cost) {
            //cout << x << "->" << y << endl;
            dfs_2(y, u_min_dist, U_dist);
            u_min_dist[x] = min(u_min_dist[x], u_min_dist[y]);
        } 
    }
}


LL solve() {
    Dist u_min_dist(N + 1, INF);
    Dist v_min_dist(N + 1, INF);

    dfs_2(S, u_min_dist, U_dist);
    dfs_2(S, v_min_dist, V_dist);

    LL ans = INF;
    FOE(x, 1, N) {
        ans = min(ans, u_min_dist[x] + V_dist[x]);
        ans = min(ans, v_min_dist[x] + U_dist[x]);
    }
    return ans;
}


int main() {
    int A, B, C;
    cin >> N >> M >> S >> T >> U >> V;

    G.resize(N + 1);
    FOR(_, 0, M) {
        cin >> A >> B >> C;
        G[A].PB({B, C});
        G[B].PB({A, C});
    }

    S_dist = compute_shortest_path(G, {S}, N);
    T_dist = compute_shortest_path(G, {T}, N);
    U_dist = compute_shortest_path(G, {U}, N);
    V_dist = compute_shortest_path(G, {V}, N);
    //cout << src_dist[T] << " " << dst_dist[S] << endl;

    ST_shortest_path_cost = S_dist[T];
    assert (S_dist[T] == T_dist[S]);

    // Case 1: Travel U -> some nodes along a shortest path -> V
    LL ans = solve();
    //cout << ans << endl;

    // Case 2: Travel U -> V via direct shortest path
    ans = min(ans, U_dist[V]);

    cout << ans << endl;

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 15364 KB Output is correct
2 Correct 665 ms 14296 KB Output is correct
3 Correct 700 ms 18164 KB Output is correct
4 Correct 631 ms 15308 KB Output is correct
5 Correct 653 ms 14052 KB Output is correct
6 Correct 679 ms 15536 KB Output is correct
7 Correct 701 ms 14024 KB Output is correct
8 Correct 673 ms 13900 KB Output is correct
9 Correct 675 ms 14056 KB Output is correct
10 Correct 607 ms 13912 KB Output is correct
11 Correct 284 ms 13124 KB Output is correct
12 Correct 699 ms 13996 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 15552 KB Output is correct
2 Correct 679 ms 15744 KB Output is correct
3 Correct 671 ms 15272 KB Output is correct
4 Correct 682 ms 15628 KB Output is correct
5 Correct 677 ms 16124 KB Output is correct
6 Correct 678 ms 17488 KB Output is correct
7 Correct 688 ms 17748 KB Output is correct
8 Correct 691 ms 15692 KB Output is correct
9 Correct 657 ms 16176 KB Output is correct
10 Correct 701 ms 15404 KB Output is correct
11 Correct 294 ms 14584 KB Output is correct
12 Correct 765 ms 17816 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1024 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 70 ms 1600 KB Output is correct
5 Correct 36 ms 1016 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 8 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 36 ms 1064 KB Output is correct
11 Correct 7 ms 380 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 4 ms 380 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 15364 KB Output is correct
2 Correct 665 ms 14296 KB Output is correct
3 Correct 700 ms 18164 KB Output is correct
4 Correct 631 ms 15308 KB Output is correct
5 Correct 653 ms 14052 KB Output is correct
6 Correct 679 ms 15536 KB Output is correct
7 Correct 701 ms 14024 KB Output is correct
8 Correct 673 ms 13900 KB Output is correct
9 Correct 675 ms 14056 KB Output is correct
10 Correct 607 ms 13912 KB Output is correct
11 Correct 284 ms 13124 KB Output is correct
12 Correct 699 ms 13996 KB Output is correct
13 Correct 678 ms 15552 KB Output is correct
14 Correct 679 ms 15744 KB Output is correct
15 Correct 671 ms 15272 KB Output is correct
16 Correct 682 ms 15628 KB Output is correct
17 Correct 677 ms 16124 KB Output is correct
18 Correct 678 ms 17488 KB Output is correct
19 Correct 688 ms 17748 KB Output is correct
20 Correct 691 ms 15692 KB Output is correct
21 Correct 657 ms 16176 KB Output is correct
22 Correct 701 ms 15404 KB Output is correct
23 Correct 294 ms 14584 KB Output is correct
24 Correct 765 ms 17816 KB Output is correct
25 Correct 38 ms 1024 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 3 ms 376 KB Output is correct
28 Correct 70 ms 1600 KB Output is correct
29 Correct 36 ms 1016 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 8 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 36 ms 1064 KB Output is correct
35 Correct 7 ms 380 KB Output is correct
36 Correct 1 ms 376 KB Output is correct
37 Correct 3 ms 376 KB Output is correct
38 Correct 5 ms 376 KB Output is correct
39 Correct 4 ms 380 KB Output is correct
40 Correct 680 ms 15320 KB Output is correct
41 Correct 725 ms 14096 KB Output is correct
42 Correct 657 ms 14080 KB Output is correct
43 Correct 319 ms 13680 KB Output is correct
44 Correct 304 ms 13676 KB Output is correct
45 Correct 653 ms 13876 KB Output is correct
46 Correct 600 ms 13968 KB Output is correct
47 Correct 647 ms 15128 KB Output is correct
48 Correct 286 ms 11664 KB Output is correct
49 Correct 561 ms 15256 KB Output is correct
50 Correct 622 ms 13792 KB Output is correct
51 Correct 620 ms 13924 KB Output is correct