Submission #1277745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277745		ssseul	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	220 ms	20612 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

// Dùng hằng số để code dễ đọc và bảo trì hơn
constexpr int MAXN = 100001;
// Định nghĩa giá trị vô cực cho kiểu long long
constexpr long long INF = std::numeric_limits<long long>::max();

typedef long long ll;
using namespace std;

// === Biến toàn cục ===
int N, M; // Số đỉnh và số cạnh
int S, T, U, V; // Các đỉnh đặc biệt

// Danh sách kề: graph[i] chứa các cặp {đỉnh kề, trọng số}
vector<pair<ll, ll>> graph[MAXN];

// Mảng lưu khoảng cách:
// du[i]: khoảng cách ngắn nhất từ U đến i
// dv[i]: khoảng cách ngắn nhất từ V đến i
vector<ll> du(MAXN);
vector<ll> dv(MAXN);

// Biến lưu kết quả cuối cùng
ll ans;

// === Hàm Dijkstra chuẩn ===
// Tìm đường đi ngắn nhất từ một đỉnh `start` đến tất cả các đỉnh khác.
// Kết quả được lưu vào mảng `dist`.
void dijkstra(int start, vector<ll>& dist) {
    // 1. Khởi tạo
    // Điền tất cả khoảng cách là vô cực
    dist.assign(N + 1, INF);
    // Khoảng cách từ đỉnh bắt đầu đến chính nó là 0
    dist[start] = 0;

    // Priority queue (min-heap) lưu các cặp {khoảng cách, đỉnh}
    // Dùng `greater` để biến nó thành min-heap
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, start});

    // 2. Vòng lặp chính của Dijkstra
    while (!pq.empty()) {
        // Lấy đỉnh có khoảng cách nhỏ nhất ra khỏi hàng đợi
        ll d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // Tối ưu hóa: Nếu khoảng cách đã lưu cũ hơn, bỏ qua
        if (d > dist[u]) {
            continue;
        }

        // 3. Duyệt các đỉnh kề (relax edges)
        for (auto& edge : graph[u]) {
            int v_neighbor = edge.first;
            ll weight = edge.second;

            // Nếu tìm thấy đường đi tốt hơn đến v_neighbor
            if (dist[u] + weight < dist[v_neighbor]) {
                dist[v_neighbor] = dist[u] + weight;
                pq.push({dist[v_neighbor], v_neighbor});
            }
        }
    }
}

// === Hàm Dijkstra sửa đổi để giải quyết bài toán ===
// Tìm đường đi ngắn nhất từ `start` đến `end`, đồng thời tối ưu hóa một tiêu chí phụ.
// Tiêu chí phụ: Tìm đường đi ngắn nhất có tổng (min(du) + min(dv)) trên đường đi là nhỏ nhất.
void solve_path(int start, int end) {
    // Mảng lưu đường đi ngắn nhất từ `start`
    vector<ll> dist_from_start(N + 1, INF);
    // dp[0][i]: giá trị du[] nhỏ nhất trên đường đi ngắn nhất từ `start` đến `i`
    vector<ll> min_du_on_path(N + 1, INF);
    // dp[1][i]: giá trị dv[] nhỏ nhất trên đường đi ngắn nhất từ `start` đến `i`
    vector<ll> min_dv_on_path(N + 1, INF);

    dist_from_start[start] = 0;
    min_du_on_path[start] = du[start];
    min_dv_on_path[start] = dv[start];

    // Priority queue lưu {khoảng cách, đỉnh}
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, start});

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

        if (d > dist_from_start[u]) {
            continue;
        }

        for (auto& edge : graph[u]) {
            int v_neighbor = edge.first;
            ll weight = edge.second;

            ll new_dist = dist_from_start[u] + weight;
            // Tính giá trị min_du và min_dv mới nếu đi qua cạnh (u, v_neighbor)
            ll new_min_du = min(min_du_on_path[u], du[v_neighbor]);
            ll new_min_dv = min(min_dv_on_path[u], dv[v_neighbor]);

            // Trường hợp 1: Tìm thấy một đường đi NGẮN HƠN đến v_neighbor
            if (new_dist < dist_from_start[v_neighbor]) {
                dist_from_start[v_neighbor] = new_dist;
                min_du_on_path[v_neighbor] = new_min_du;
                min_dv_on_path[v_neighbor] = new_min_dv;
                pq.push({new_dist, v_neighbor});
            }
            // Trường hợp 2: Tìm thấy một đường đi khác CÓ CÙNG ĐỘ DÀI ngắn nhất
            else if (new_dist == dist_from_start[v_neighbor]) {
                // Ta kiểm tra xem đường đi mới này có tốt hơn về tiêu chí phụ không
                if (new_min_du + new_min_dv < min_du_on_path[v_neighbor] + min_dv_on_path[v_neighbor]) {
                    min_du_on_path[v_neighbor] = new_min_du;
                    min_dv_on_path[v_neighbor] = new_min_dv;
                    // Đẩy lại vào PQ để xét các đường đi tiếp theo từ đỉnh này
                    // với giá trị tiêu chí phụ đã được cải thiện.
                    pq.push({new_dist, v_neighbor});
                }
            }
        }
    }
    
    // Sau khi thuật toán kết thúc, nếu có đường đi đến `end`
    if (dist_from_start[end] != INF) {
        // Cập nhật kết quả toàn cục
        ans = min(ans, min_du_on_path[end] + min_dv_on_path[end]);
    }
}


int main() {
    // Tăng tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    // 1. Chạy Dijkstra thông thường từ U và V để tính trước khoảng cách
    // du[i] và dv[i] cho mọi đỉnh i.
    dijkstra(U, du);
    dijkstra(V, dv);

    // 2. Khởi tạo kết quả ban đầu. Một trường hợp có thể xảy ra là
    // đường đi tối ưu không cần đi qua S và T, mà chỉ cần nối U và V.
    ans = du[V];

    // 3. Chạy thuật toán Dijkstra sửa đổi để tìm đường đi từ S->T và T->S
    // và cập nhật kết quả.
    solve_path(S, T);
    solve_path(T, S);

    cout << ans << '\n';

    return 0;
}

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