제출 #160056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160056		XCoder	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	857 ms	21700 KiB

commuter_pass

// https://oj.uz/problem/view/JOI18_commuter_pass (Accepted + Cleaned up)
#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(int x, Dist &v_min_dist, Dist &V_dist) {
    // DFS - traverse all possible shortest paths

    // Already tried
    if (v_min_dist[x] != INF) return;

    // x = current node
    // v_min_dist[x] = x -~~> some node y -~~> U
    //                 where dist(y, U) is minimized

    v_min_dist[x] = V_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(y, v_min_dist, V_dist);
            v_min_dist[x] = min(v_min_dist[x], v_min_dist[y]);
        } 
    }
}


LL solve() {
    // Case 1: Travel U -> V via direct shortest path
    LL ans = U_dist[V];

    // Case 2: Travel U -> some nodes along a shortest path -> V
    Dist u_min_dist(N + 1, INF);
    Dist v_min_dist(N + 1, INF);

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

    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]);

    LL ans = solve();
    cout << ans << endl;

    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45