Submission #1121240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121240		LonlyR	Cities (BOI16_cities)	C++17	74 / 100	6044 ms	233352 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;
vector<int> ok;

    #define iii array<ll, 3>
    ll d[32][maxn];
    void full()
    {
        priority_queue<iii, vector<iii>, greater<iii>> pq;
        memset(d, 0x3f, sizeof d);
        ll oo = d[0][0];
        for (int i = 1; i <= n; i++)
        {
            int bit = 0;
            if (chosen[i])
                bit = 1 << (chosen[i] - 1);
            else continue;
            d[bit][i] = 0;
            pq.push({0, i, bit});
        }
        int full = (1 << k) - 1;
        while (pq.size())
        {
            auto to = pq.top();
            pq.pop();
            ll val = to[0], u = to[1], bit = to[2];
            if (val != d[bit][u]) continue;
            for (auto i : adj[u])
            {
                ll v, w;
                tie(v, w) = i;
                int not_mask = bit ^ full;
                if(d[bit][v] > val + w)
                    pq.push({d[bit][v] = val + w, v, bit});
                for(int s = not_mask; s > 0; s = (s - 1) & not_mask)
                    if(d[bit | s][v] > val + d[s][v] + w)
                        pq.push({d[bit | s][v] = val + d[s][v] + w, v, bit | s});
            }
        }
        ll res = oo;
        for (int i = 1; i <= n; i++)
            res = min(res, d[full][i]);
        cout << res;
    }


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;
    for (int i = 1, x; i <= k; i++)
        cin >> x, chosen[x] = 1;
    k = accumulate(chosen + 1, chosen + n + 1, 0ll);
    for (int i = 1; i <= n; i++)
        if (chosen[i])
            ok.emplace_back(i),
            chosen[i] = ok.size();
    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),
        edges.push_back({w, u, v});
    full();
}

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