Submission #485815

#	Time	Username	Problem	Language	Result	Execution time	Memory
485815		Rainbowbunny	Cities (BOI16_cities)	C++17	100 / 100	1858 ms	47384 KiB

cities

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

const int MAXN = 1e5 + 5;
const long long INF = 1e18;

int n, m, k;
long long dp[32][MAXN];
vector <pair <int, long long> > Adj[MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i < 32; i++)
    {
        for(int j = 0; j < MAXN; j++)
        {
            dp[i][j] = INF;
        }
    }
    for(int i = 0; i < k; i++)
    {
        int id;
        cin >> id;
        dp[1 << i][id] = 0;
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        Adj[u].emplace_back(v, c);
        Adj[v].emplace_back(u, c);
    }
    for(int i = 1; i < (1 << k); i++)
    {
        for(int mask = i; mask > 0; mask = (mask - 1) & i)
        {
            if(mask == i)
            {
                continue;
            }
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i][j], dp[i ^ mask][j] + dp[mask][j]);
            }
        }
        priority_queue <pair <long long, int> > pq;
        for(int j = 1; j <= n; j++)
        {
            if(dp[i][j] != INF)
            {
                pq.emplace(-dp[i][j], j);
            }
        }
        while(pq.empty() == false)
        {
            long long d = -pq.top().first, v = pq.top().second;
            pq.pop();
            if(d != dp[i][v])
            {
                continue;
            }
            for(auto x : Adj[v])
            {
                if(dp[i][x.first] > d + x.second)
                {
                    dp[i][x.first] = d + x.second;
                    pq.emplace(-dp[i][x.first], x.first);
                }
            }
        }
    }
    cout << *min_element(dp[(1 << k) - 1] + 1, dp[(1 << k) - 1] + n + 1) << '\n';
}

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