Submission #969156

#	Time	Username	Problem	Language	Result	Execution time	Memory
969156		vjudge1	Cities (BOI16_cities)	C++17	100 / 100	4664 ms	40400 KiB

cities

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 33;
const long long INF = 1e18;
vector<pair<int,int>> vec[N];
long long dis[N][K] , ans = INF;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k,m; cin >> n >> k >> m;
    int all = 1<<k;
    for (int i=0;i<all;i++) {
        for (int j=1;j<=n;j++) {
            dis[j][i] = INF;
        }
    }
    for (int i=0;i<k;i++) {
        int a; cin >> a;
        dis[a][1<<i] = 0;
    }
    while (m--) {
        int u,v,w; cin >> u >> v >> w;
        vec[u].push_back({w, v});
        vec[v].push_back({w, u});
    }
    for (int b1=1;b1<all;b1++) {
        for (int b2=1;b2<b1;b2<<=1) {
            if (b1&b2==0) continue;
            for (int i=1;i<=n;i++) {
                dis[i][b1] = min(dis[i][b1], dis[i][b2] + dis[i][b1^b2]);
            }
        }
        
        for (int i=1;i<=n;i++) {
            if (dis[i][b1]==INF) continue;
            q.push({dis[i][b1], i});
        }
        while (!q.empty()) {
            auto [dist,u] = q.top(); q.pop();
            for (auto [w,v]:vec[u]) {
                if (dis[v][b1] > dis[u][b1] + w) {
                    dis[v][b1] = dis[u][b1] + w;
                    q.push({dis[v][b1], v});
                }
            }
        }
    }
    for (int i=1;i<=n;i++) ans = min(ans, dis[i][all-1]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:30:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |             if (b1&b2==0) continue;
      |                    ~~^~~

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