Submission #1121257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121257		LonlyR	Cities (BOI16_cities)	C++17	74 / 100	6065 ms	164716 KiB

cities

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 1e5 + 5;
int n, k, m;
int chosen[maxn];
vector<pair<int,int>> adj[maxn];
vector<array<int, 3>> edges;

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        } return false;
    }
vector<int> ok;

#define iii tuple<ll,int,int>
ll d[32][maxn];



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> k >> m;
    priority_queue<iii, vector<iii>, greater<iii>> pq;
    ll oo = 2e18;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < 1 << k;j++)
            d[j][i] = oo;
    for (int i = 1, x; i <= k; i++)
    {
        cin >> x;
        chosen[x] = 1;
        ok.emplace_back(x);
        d[1 << (i - 1)][x] = 0;
        pq.emplace(0, x, 1 << (i - 1));
    }
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w,
        adj[u].emplace_back(v, w),
        adj[v].emplace_back(u, w);

    int full = (1 << k) - 1;
    while (pq.size())
    {
        auto to = pq.top();
        pq.pop();
        ll val; int u, mask;
        tie(val, u, mask) = to;
        if (val != d[mask][u]) continue;
        for (auto it : adj[u]) {
            int v, w; tie(v, w) = it;
            for (int supr = mask; supr < (1 << k); supr = (supr + 1) | mask) {
                if (d[supr ^ mask][v] == oo) continue;
                if (d[mask][u] + d[supr ^ mask][v] + w < d[supr][v]) {
                    d[supr][v] = d[mask][u] + d[supr ^ mask][v] + w;
                    pq.emplace(d[supr][v], v, supr);
                }
            }
        }
    }
    ll res = oo;
    for (int i : ok)
        res = min(res, d[full][i]);
    cout << res;
}

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