Submission #1278814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278814		linhhnt11072010	Cities (BOI16_cities)	C++20	100 / 100	1632 ms	44716 KiB

cities

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

typedef long long ll;

const ll INF = 1000000000000000000LL; // 1e18

ll n, m, k;
ll a[10];
vector< pair<ll,ll> > vt[100009];
ll kq[1<<10][100009]; // k <= 10

struct Node {
    ll d;
    int u;
    Node() {}
    Node(ll _d,int _u){d=_d; u=_u;}
    bool operator<(const Node &other) const { return d > other.d; } // min-heap
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> m;
    for(int i=1;i<=k;i++) cin >> a[i];

    for(int i=1;i<=m;i++){
        ll u, v, c;
        cin >> u >> v >> c;
        vt[u].push_back(make_pair(v,c));
        vt[v].push_back(make_pair(u,c));
    }

    // init DP
    for(int mask=0; mask<(1<<k); mask++)
        for(int i=1;i<=n;i++)
            kq[mask][i] = INF;

    // 1-bit mask
    for(int i=0;i<k;i++)
        kq[1<<i][a[i+1]] = 0;

    // DP trên tất cả mask
    for(int mask=1; mask<(1<<k); mask++){
        // merge subset con
        for(int sub=mask; sub; sub=(sub-1)&mask){
            ll other = mask ^ sub;
            if(other==0) continue;
            for(int u=1; u<=n; u++){
                if(kq[sub][u]==INF) continue;
                for(int i=0;i<vt[u].size();i++){
                    ll v = vt[u][i].first;
                    ll cost = vt[u][i].second;
                    if(kq[other][v]==INF) continue;
                    if(kq[mask][v] > kq[sub][u] + cost + kq[other][v])
                        kq[mask][v] = kq[sub][u] + cost + kq[other][v];
                }
            }
        }

        // Dijkstra trong mask
        priority_queue<Node> pq;
        for(int i=1;i<=n;i++)
            if(kq[mask][i]!=INF) pq.push(Node(kq[mask][i],i));

        while(!pq.empty()){
            Node tmp = pq.top(); pq.pop();
            ll d = tmp.d;
            int u = tmp.u;
            if(d != kq[mask][u]) continue;
            for(int i=0;i<vt[u].size();i++){
                ll v = vt[u][i].first;
                ll c = vt[u][i].second;
                if(kq[mask][v] > d + c){
                    kq[mask][v] = d + c;
                    pq.push(Node(kq[mask][v],v));
                }
            }
        }
    }

    ll res = INF;
    for(int i=1;i<=n;i++)
        if(kq[(1<<k)-1][i] < res) res = kq[(1<<k)-1][i];

    cout << res << "\n";
    return 0;
}

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