Submission #84260

#	Time	Username	Problem	Language	Result	Execution time	Memory
84260		Flying_dragon_02	Cities (BOI16_cities)	C++14	74 / 100	3274 ms	263168 KiB

cities

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 1e5 + 5;

long long f[N][(1 << 5)];

int n, k, m;

vector<int> vec[(1 << 5)];
typedef pair<long long, ii> pii;

priority_queue<pii, vector<pii>, greater<pii>> pq;

vector<ii> graph[N];

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> k >> m;
    for(int mask1 = 0; mask1 < (1 << k); mask1++) {
        for(int mask2 = 0; mask2 < (1 << k); mask2++) {
            if(!(mask1 & mask2))
                vec[mask1].pb(mask2);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (1 << k); j++)
            f[i][j] = LLONG_MAX;
    }
    for(int i = 1; i <= n; i++)
        f[i][0] = 0;
    for(int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        f[x][(1 << (i - 1))] = 0;
        pq.push({0, {x, (1 << (i - 1))}});
    }
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].pb({v, c});
        graph[v].pb({u, c});
    }
    while(!pq.empty()) {
        pii frt = pq.top();
        pq.pop();
        if(frt.se.se == (1 << k) - 1) {
            cout << f[frt.se.fi][frt.se.se];
            exit(0);
        }
        int u = frt.se.fi, mask = frt.se.se;
        if(frt.fi > f[u][mask]) continue;
        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].fi, w = graph[u][i].se;
            for(int j = 0; j < vec[mask].size(); j++) {
                int nmask = vec[mask][j], newmask = (mask | nmask);
                if(f[v][nmask] == LLONG_MAX) continue;
                if(f[v][newmask] > f[u][mask] + w + f[v][nmask]) {
                    f[v][newmask] = f[u][mask] + w + f[v][nmask];
                    pq.push({f[v][newmask], {v, newmask}});
                }
                if(f[u][newmask] > f[u][mask] + w + f[v][nmask]) {
                    f[u][newmask] = f[u][mask] + w + f[v][nmask];
                    pq.push({f[u][newmask], {u, newmask}});
                }
            }
        }
    }
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:61:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~
cities.cpp:63:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vec[mask].size(); j++) {
                            ~~^~~~~~~~~~~~~~~~~~

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