Submission #1245939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245939		boxfish	Cities (BOI16_cities)	C++20	100 / 100	2320 ms	47004 KiB

cities

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

int n, k, m;
ll Dis[N + 5][35];
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){
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
        for(int i = 1 ; i <= n ; ++i){
            for(int sub = mask ; sub ; sub = (sub - 1) & mask){
                Dis[i][mask] = min(Dis[i][mask],Dis[i][sub] + Dis[i][mask ^ sub]);
            }
            if(Dis[i][mask] < inf) pq.push({Dis[i][mask],i});
        }
//        cout << mask << ":\n";

        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;
//            cout << u << ',' << d << "\n";
            for(pair<int,ll> i : g[u]){
                ll w = d + i.second;
                int v = i.first;
//                cout << v << '.' << w << ' ' << Dis[v][mask] << "\n";
                if(Dis[v][mask] > w){
                    Dis[v][mask] = w;
//                    cout << "?:v\n";
                    pq.push({w,v});
                }
            }
        }
//        for(int i = 1 ; i <= n ; ++i)
//            cout << i << ' ' << Dis[i][mask] << '\n';
    }

    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: 26 / 26