Submission #97508

#	Time	Username	Problem	Language	Result	Execution time	Memory
97508		minhtung0404	Cities (BOI16_cities)	C++17	100 / 100	5105 ms	48436 KiB

cities

//https://oj.uz/problem/view/BOI16_cities

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

typedef pair <long long, int> ii;
vector <ii> G[N];
int n, k, m;
long long f[N][32], ans = inf, a[5];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < N; i++) for (int j = 0; j < 32; j++) f[i][j] = inf;
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        f[a[i]][1 << i] = 0;
    }
    while (m--){
        int u, v, c; cin >> u >> v >> c;
        G[u].push_back(ii(c, v));
        G[v].push_back(ii(c, u));
    }
    for (int mask = 1; mask < (1 << k); mask++){
        priority_queue <ii, vector <ii>, greater <ii> > mq;
        for (int i = 0; i < mask; i++){
            if ((mask | i) != mask) continue;
            int a = i ^ mask;
            if (i < a) continue;
            for (int j = 1; j <= n; j++) f[j][mask] = min(f[j][mask], f[j][i] + f[j][a]);
        }
        for (int i = 1; i <= n; i++) if (f[i][mask] != inf) mq.push(ii(f[i][mask], i));
        while (mq.size()){
            int u = mq.top().second; long long c = mq.top().first; mq.pop();
            if (c != f[u][mask]) continue;
            for (auto p : G[u]){
                int v = p.second, cost = p.first;
                if (f[v][mask] > f[u][mask] + cost){
                    f[v][mask] = f[u][mask] + cost;
                    mq.push(ii(f[v][mask], v));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) ans = min(ans, f[i][(1 << k) - 1]);
    cout << ans;
}

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