Submission #1166299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166299		vastaway	Cities (BOI16_cities)	C++20	74 / 100	6091 ms	95284 KiB

cities

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

const int N = 100001;
int tab[N][1<<5], dist[5][N];
vector<pair<int, int>> adj[N];

signed main() {
    cin.sync_with_stdio(0);
    cin.tie(0);

    int n, k, m, ans = LLONG_MAX;
    cin >> n >> k >> m;
    
    vector<int> term(k);
    for (int i = 0; i < k; i++) cin >> term[i];

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    for (int i = 0; i < k; i++) {
        fill(dist[i], dist[i] + N, LLONG_MAX);
        dist[i][term[i]] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        q.push({0, term[i]});

        while (!q.empty()) {
            auto [c, v] = q.top();
            q.pop();
            if (c != dist[i][v]) continue;

            for (auto& [nv, w] : adj[v]) {
                if (dist[i][v] + w < dist[i][nv]) {
                    dist[i][nv] = dist[i][v] + w;
                    q.push({dist[i][nv], nv});
                }
            }
        }
    }

    for (int v = 1; v <= n; v++) adj[v].push_back({v, 0});

    for (int i = 0; i < k; i++) {
        for (int j = 0; j < N; j++) fill(tab[j], tab[j] + (1 << 5), LLONG_MAX);
        tab[term[i]][1 << i] = 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;
        q.push({0, term[i], 1 << i});

        while (!q.empty()) {
            auto [c, v, mask] = q.top();
            q.pop();
            // cout << c << " " << v << " " << mask << "\n";
            if (c != tab[v][mask]) continue;
            if (mask == (1 << k) - 1) {ans = min(ans, c); break;}

            for (auto& [nv, w] : adj[v]) {
                for (int t = 0, amount = 0; t < k; t++) {
                    int nmask = mask | (1<<t);
                    if (nmask > mask) amount = dist[t][nv];
                    if (c + w + amount < tab[nv][nmask]) {
                        tab[nv][nmask] = c + w + amount;
                        q.push({tab[nv][nmask], nv, nmask});
                    }
                }
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

/*

resource: https://www.youtube.com/watch?v=BG4vAoV5kWw&t=499s
for k <= 5, >0 caterpillar graph possible
can do disjtra w/ mask and node state

tle + bad alloc. instead of extra 2^k factor edges
ensure can only retreive one terminal at a time, but rego to self for multiple terminal lines
so its only extra k factor edges

tle last batck, k = 5. hmmm...

*/

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