제출 #1277741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277741		ssseul	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	173 ms	24780 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <map>

using namespace std;

// Định nghĩa hằng số cho giá trị vô cùng lớn
const long long LL_INF = 4500000000000000000LL;

// Pair cho cạnh: {destination_node, weight}
typedef pair<int, int> Edge;
// Pair cho Dijkstra: {distance, node}
typedef pair<long long, int> State;

// Số lượng nút tối đa
const int MAXN = 100000;

int N, M, S, T, U, V;
vector<Edge> adj[MAXN];

// Mảng khoảng cách từ các nguồn khác nhau
long long distS[MAXN]; // Khoảng cách từ S
long long distU[MAXN]; // Khoảng cách từ U
long long distV[MAXN]; // Khoảng cách từ V

// Cấu trúc cho DAG của đường đi ngắn nhất từ S
vector<int> shortestPathParents[MAXN]; // Các nút cha trên đường đi ngắn nhất từ S
vector<int> shortestPathChildren[MAXN]; // Các nút con trong DAG (đảo ngược của parents)
bool reachableFromS[MAXN]; // Nút có nằm trên đường đi ngắn nhất từ S đến T không

// Hàm Dijkstra chung
void dijkstra(long long dist[], int source) {
    fill(dist, dist + N, LL_INF);
    dist[source] = 0;

    // min_heap: {distance, node}
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

// Hàm Dijkstra đặc biệt để xây dựng DAG của đường đi ngắn nhất từ S
void dijkstraWithParentTracking(long long dist[], int source) {
    fill(dist, dist + N, LL_INF);
    dist[source] = 0;

    for (int i = 0; i < N; ++i) {
        shortestPathParents[i].clear();
    }

    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            long long newDist = dist[u] + weight;

            if (newDist < dist[v]) {
                dist[v] = newDist;
                // Xóa cha cũ và thêm cha mới
                shortestPathParents[v].clear();
                shortestPathParents[v].push_back(u);
                pq.push({dist[v], v});
            } else if (newDist == dist[v]) {
                // Thêm một cha khác có thể tạo đường đi ngắn nhất
                shortestPathParents[v].push_back(u);
            }
        }
    }
}

// Các mảng memoization cho Quy hoạch động
long long memoForward[MAXN]; // dpForward(i): min cost từ V đến bất kỳ nút nào từ i trở về T trong DAG
long long memoBackward[MAXN]; // dpBackward(i): min cost từ V đến bất kỳ nút nào trên đường đi S -> i trong DAG

// DP 1: Min(distV[x]) cho x từ i đến T trong DAG
long long dpForward(int u) {
    if (memoForward[u] != -1) return memoForward[u];
    
    // Base case: chính nó
    long long best = distV[u];

    // Truy hồi: tìm min trong số các con trong DAG
    for (int v : shortestPathChildren[u]) {
        best = min(best, dpForward(v));
    }
    
    return memoForward[u] = best;
}

// DP 2: Min(distV[x]) cho x từ S đến i trong DAG
long long dpBackward(int u) {
    if (memoBackward[u] != -1) return memoBackward[u];
    
    // Base case: chính nó
    long long best = distV[u];
    
    // Truy hồi: tìm min trong số các cha trong DAG
    for (int v : shortestPathParents[u]) {
        best = min(best, dpBackward(v));
    }
    
    return memoBackward[u] = best;
}


void solve() {
    // Đọc input
    cin >> N >> M >> S >> T >> U >> V;
    // Chuyển sang chỉ số 0
    --S; --T; --U; --V;

    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c}); // Đồ thị vô hướng
    }

    // 1. Tính khoảng cách từ U và V
    dijkstra(distU, U);
    dijkstra(distV, V);

    // 2. Tính khoảng cách từ S và xây dựng DAG của đường đi ngắn nhất từ S
    dijkstraWithParentTracking(distS, S);

    // 3. Xây dựng mảng con trong DAG (shortestPathChildren) và xác định nút reachable
    fill(memoForward, memoForward + N, -1);
    fill(memoBackward, memoBackward + N, -1);
    fill(reachableFromS, reachableFromS + N, false);
    for (int i = 0; i < N; ++i) {
        shortestPathChildren[i].clear();
    }

    // BFS ngược từ T để chỉ xét các nút nằm trên đường đi S -> T
    queue<int> q; 
    if (distS[T] != LL_INF) { // Chỉ bắt đầu nếu T có thể truy cập được từ S
        q.push(T);
    }
    
    while (!q.empty()) {
        int u = q.front(); q.pop();

        if (!reachableFromS[u]) {
            reachableFromS[u] = true;
            for (int v : shortestPathParents[u]) {
                // v là cha của u trên đường đi ngắn nhất S -> T
                shortestPathChildren[v].push_back(u); 
                q.push(v);
            }
        }
    }
    
    // 4. Tính toán kết quả
    // Ứng viên 1: U -> V trực tiếp (nếu có)
    long long min_cost = distU[V]; 

    // Ứng viên 2: U -> i -> (trục trặc của V) -> T
    // i là một nút trên DAG của đường đi ngắn nhất S->T
    for (int i = 0; i < N; ++i) {
        if (reachableFromS[i] && distU[i] != LL_INF) {
            
            // Chi phí cho V là min(chi phí thoát sớm, chi phí thoát muộn)
            // Chi phí thoát sớm (Backward): V đi đến một nút x trên đường S->i
            // Chi phí thoát muộn (Forward): V đi đến một nút x trên đường i->T
            long long cost_V = min(dpForward(i), dpBackward(i));

            // Tổng chi phí: U đi đến i + chi phí V
            min_cost = min(min_cost, distU[i] + cost_V);
        }
    }

    // 5. In kết quả
    cout << min_cost << endl;
}

int main() {
    // Tối ưu hóa I/O
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

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