Submission #1245892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245892		boxfish	Cities (BOI16_cities)	C++20	0 / 100	114 ms	65596 KiB

cities

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

int n, k, m;
ll Dis[N + 5][(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);
    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;
    }

    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});
    }
    for(int mask = 1 ; mask < (1 << k) ; ++mask){
        for(int sub = ((mask - 1) & mask) ; sub ; sub = (sub - 1) & mask){
            int other = (mask ^ sub);
            for(int v = 1 ; v <= n ; ++v)
                Dis[v][mask] = min(Dis[v][mask],Dis[v][sub] + Dis[v][other]);
        }
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        for(int v = 1 ; v <= n ; ++v)
        if(Dis[v][mask] < inf) pq.push({Dis[v][mask],v});

        while(!pq.empty()){
            pair<ll,int> t = pq.top();
            pq.pop();
            int u = t.second;
            ll d = t.first;

            if(d != Dis[u][mask]) continue;

            for(pair<int,ll> i : g[u]){
                ll w = d + i.second;
                int v = i.first;
                if(Dis[v][mask] > w){
                    Dis[v][mask] = w;
                    pq.push({v,w});
                }
            }
        }
    }

    ll ans = inf;
    for(int i = 1 ; i <= n ; ++i)
        ans = min(ans,Dis[i][(1 << k) - 1]);
    cout << ans;
    return 0;
}

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