Submission #971951

#	Time	Username	Problem	Language	Result	Execution time	Memory
971951		jadai007	Cities (BOI16_cities)	C++17	100 / 100	3236 ms	54216 KiB

cities

#include<bits/stdc++.h>
#define int long long

using namespace std;

int dis[100100][40], u, v, w, n, m, k;
vector<pair<int, int>> vc[100100];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> m;
    for(int i = 1; i<=n; ++i) for(int j = 0; j<(1 << k); ++j) dis[i][j] = 1e18;
    for(int i = 0; i<k; ++i){
        int a; cin >> a;
        dis[a][(1 << i)] = 0;
    }
    for(int i = 1; i<=m; ++i){
        cin >> u >> v >> w;
        vc[u].emplace_back(v, w);
        vc[v].emplace_back(u, w);
    }
    for(int mask = 0; mask < (1 << k); ++mask){
        for(int i = 0; i<k; ++i){
            if(mask&(1 << i)){
                for(int j = 1; j<=n; ++j) dis[j][mask] = min(dis[j][mask], dis[j][mask^(1 << i)] + dis[j][(1 << i)]);
            }
        }
        for(int i = 1; i<=n; ++i) pq.emplace(dis[i][mask], i);
        while(!pq.empty()){
            int w = pq.top().first, u = pq.top().second;
            pq.pop();
            for(auto x:vc[u]){
                int v = x.first, ww = x.second;
                if(dis[v][mask] > dis[u][mask] + ww){
                    dis[v][mask] = dis[u][mask] + ww;
                    pq.emplace(dis[v][mask], v);
                }
            }
        }
    }
    int ans = 1e18;
    for(int i = 1; i<=n; ++i) ans = min(ans, dis[i][(1 << k) - 1]);
    cout << ans;
}

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:31:17: warning: unused variable 'w' [-Wunused-variable]
   31 |             int w = pq.top().first, u = pq.top().second;
      |                 ^

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