제출 #1288212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288212		phungha	Cities (BOI16_cities)	C++20	100 / 100	1213 ms	40500 KiB

cities

#include <bits/stdc++.h>
using namespace std;

int n, k, m, city[5];
vector<pair<int, int>> g[100001];
long long d[32][100001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("test24.in", "r", stdin);
    //freopen("test01.out", "w", stdout);
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) {
        cin >> city[i];
        city[i]--; // chuyển về chỉ số 0
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--; // chuyển về chỉ số 0
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    /*
    d[mask][v] = chi phí nhỏ nhất để tạo một miền liên thông (một cây con) kết nối các đỉnh quan trọng trong mask
    và tập đó kết thúc / gom về tại đỉnh v:
        + mask là bitmask trên k đỉnh quan trọng (bit i = 1: tập này đã kết nối chứa thành phố quan trọng thứ i)
        + v là một đỉnh bất kỳ trong đồ thị (0..n-1)
    khởi tạo toàn bộ mảng d với +oo
    khởi tạo trạng thái ban đầu, với mỗi thành phố quan trọng city[i]:
        + mask chỉ chứa duy nhất bit i: (1 << i)
        + chi phí để kết thúc ở chính nó là 0 (không cần cạnh nào)
    */
    for (int i = 0; i < (1 << k); i++)
        for (int j = 0; j < n; j++)
            d[i][j] = 1e18;
    for (int i = 0; i < k; ++i)
        d[1 << i][city[i]] = 0;

    // duyệt qua tất cả các mask khác 0 (1..(1<<k)-1)
    for (int mask = 1; mask < (1 << k); mask++) {
        // 1) Subset DP: ghép các tập con a và b của mask để cải thiện d[mask][v]
        // a là một tập con của mask
        for (int a = 0; a <= mask; a++) {
            if ((a | mask) != mask) continue; // điều kiện a là tập con của mask
            int b = mask ^ a;                 // b là tập con còn lại (b = mask \ a)
            if (b > a) continue;              // tránh đếm lặp (a, b) và (b, a)

            // với mỗi đỉnh v, ghép hai cây con có cùng "điểm tụ" v
            // d[mask][v] = min(d[mask][v], d[a][v] + d[b][v])
            for (int v = 0; v < n; v++)
                d[mask][v] = min(d[mask][v], d[a][v] + d[b][v]);
        }

        // 2) Dijkstra đa nguồn cho tập nguồn mask
        // Sau bước ghép ở trên, d[mask][v] hiện tại là chi phí tốt nhất để kết nối mask và "tụ" tại v, nhưng chưa lan qua các cạnh
        // pq là hàng đợi ưu tiên cho dijkstra: lưu (-cost, v) để dùng max-heap giả lập min-heap
        // đẩy các đỉnh v có d[mask][v] < +oo vào priority queue làm nguồn ban đầu
        priority_queue<pair<long long, int>> pq;
        for (int v = 0; v < n; v++)
            if (d[mask][v] < 1e18)
                pq.push({-d[mask][v], v});
        // chạy dijkstra với các nguồn đa điểm
        while (!pq.empty()) {
            long long cur_d = -pq.top().first;
            int v = pq.top().second;
            pq.pop();
            if (cur_d > d[mask][v]) continue; // đã xử lý v rồi
            for (auto [u, w]: g[v]) // relax tất cả các cạnh xuất phát từ v
                if (d[mask][u] > d[mask][v] + w) {
                    d[mask][u] = d[mask][v] + w;
                    pq.push({-d[mask][u], u});
                }
        }
    }

    // kết quả là min(d[(1 << k) - 1][v] với mọi v = 0..n-1)
    long long ans = 1e18;
    int full_mask = (1 << k) - 1;
    for (int v = 0; v < n; ++v)
        ans = min(ans, d[full_mask][v]);
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26