Submission #708175

#	Time	Username	Problem	Language	Result	Execution time	Memory
708175		phamduchung	Cities (BOI16_cities)	C++14	100 / 100	1742 ms	71668 KiB

cities

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<long long, int>
const ll N = 1e5+8;
const ll inf = 1e9 + 7;
int n, k, m;
vector<int> imp;
vector<pii> adj[N];
ll f[1<<6][N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(ll f[N]) {
    for (int i = 1; i <= n; i++) {
        if (f[i] < 1e16) pq.push({f[i], i});
    }

    while (!pq.empty()) {
        ll d;
        int u;
        tie(d, u) = pq.top();
        pq.pop();
        if (d != f[u]) continue;
        for (auto e : adj[u]) {
            int v, w;
            tie(v, w) = e;
            if (f[v] > d + w) {
                f[v] = d + w;
                pq.push({f[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    memset(f, inf, sizeof(f));
    memset(f[0], 0, sizeof(f[0]));
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) {
        int tmp;
        cin >> tmp;
        imp.push_back(tmp);
        f[1 << (i - 1)][tmp] = 0;
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int mask = 1; mask < (1 << k); mask++) {
        for (int pos = 0; pos < k; pos++) {
            if (!((mask >> pos) & 1)) continue;
            for (int i = 1; i <= n; i++) {
                f[mask][i] = min(f[mask][i], f[mask ^ (1 << pos)][i] + f[(1 << pos)][i]);
            }
        }

        dijkstra(f[mask]);
    }
    cout << *min_element(f[(1 << k) - 1] + 1, f[(1 << k) - 1] + n + 1);
    return 0;
}

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