Submission #1245783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245783		idk123321	Cities (BOI16_cities)	C++20	100 / 100	1637 ms	63452 KiB

cities

#include<bits/stdc++.h>
#define ll long long
#define pi pair<ll,ll>
#define fi first
#define se second
using namespace std;
ll n,k,m,dist[6][100005],dp[50][100005],ans = 1e18,u,v,w,x[10],dd[100005];
vector <pi> adj[100005];
void dijkstra(ll i)
{
    dist[i][x[i]] = 0;
    priority_queue<pi, vector<pi>, greater<pi> > pq;
    pq.push({0,x[i]});
    while(!pq.empty())
    {
        auto [du,u] = pq.top();
        pq.pop();
        if(du != dist[i][u]) continue;
        for(auto [v,dv] : adj[u])
        {
            if(dist[i][v] > dist[i][u] + dv)
            {
                dist[i][v] = dist[i][u] + dv;
                pq.push({dist[i][v],v});
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i < k; i++)
    {
        cin >> x[i];
        dd[x[i]] = i;
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    memset(dist, 0x3f, sizeof dist);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < k; i++)
    {
        dijkstra(i);
    }
    for(int i = 0; i < k; i++)
    {
        for(int j = 1; j <= n; j++)
        dp[1 << i][j] = dist[i][j];
    }
    for(int mask = 0; mask < (1<<k); mask++)
    {
        for(int sub = mask; sub; sub = (sub -1)&mask)
        {
            if(sub == 0 || sub == mask) continue;
            for(int v = 1; v <= n; v++)
            {
                dp[mask][v] = min(dp[sub][v] + dp[mask^sub][v],dp[mask][v]);
            }
        }
        priority_queue<pi, vector<pi>, greater<pi> > pq;
        for(int i = 1; i <= n; i++)
        {
            if(dp[mask][i] < 1e18)
            {
                pq.push({dp[mask][i], i});
            }
        }
        while(!pq.empty())
        {
            auto [du, u] = pq.top(); pq.pop();
            if(du != dp[mask][u]) continue;
            for(auto [v, w] : adj[u]) {
                if(dp[mask][v] > dp[mask][u] + w) {
                    dp[mask][v] = dp[mask][u] + w;
                    pq.push({dp[mask][v], v});
                }
            }
        }
    }
    for(int i = 1; i <= n; i++)
        ans = min(ans,dp[(1<<k)-1][i]);
    cout << ans;
}

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