Submission #1245879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245879		boxfish	Cities (BOI16_cities)	C++20	74 / 100	6097 ms	262612 KiB

cities

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 2e18;
const int N = 2e5;

int n, k, m;
ll Dis[N][(1 << 6)];
struct Node{
    int u;
    ll w;
    int mask;
    bool operator < (const Node&other) const{
        return w > other.w;
    }
};
vector<pair<int,ll>> g[N + 5];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    priority_queue<Node> pq;
    cin >> n >> k >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int _ = 0 ; _ < (1 << k) ; ++_){
            Dis[i][_] = inf;
        }

    for(int i = 0 ; i < k ; ++i){
        int x; cin >> x;
        Dis[x][(1 << i)] = 0;
        pq.push({x,0,(1 << i)});
    }
    for(int i = 1 ; i <= m ; ++i){
        int x,y;
        ll z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }

    while(!pq.empty()){
        Node t = pq.top();
        pq.pop();
        int u = t.u;
        ll w = t.w;
        int mask = t.mask;
        if(w != Dis[u][mask]) continue;
//        cout << u << ' ' << w << ' ' << mask << "\n";

        for(pair<int,ll> i : g[u]){
            ll X = w + i.second;
            if(Dis[i.first][mask] > X){
                Dis[i.first][mask] = X;
                pq.push({i.first,X,mask});
            }
        }
        int avail = ((1 << k) - 1) ^ mask;
        for(int _ = avail ; _ > 0 ; _ = (_ - 1) & avail){
            ll X = w + Dis[u][_];

            if(X < Dis[u][mask | _]){
                Dis[u][mask | _] = X;
                pq.push({u,X,(mask | _)});
            }
        }
    }
    ll ans = inf;
    for(int i = 1 ; i <= n ; ++i)
        ans = min(ans,Dis[i][(1 << k) - 1]);
    cout << ans;
    return 0;
}

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