Submission #1268141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268141		huypham2009	Cities (BOI16_cities)	C++20	100 / 100	1222 ms	44652 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18;
const int maxn=1e5+5;
int32_t MASK(int n)
{
    return 1<<n;
}
int n,k,m,dp[(1<<5)][maxn],imv[5];
vector<pair<int,int>>g[maxn];
void dijsktra(int *dist)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=1;i<=n;i++)
    {
        if(dist[i]!=INF)    
            pq.push({dist[i],i});
    }
    while(!pq.empty())
    {
        pair<int,int>tmp=pq.top();  pq.pop();
        int d=tmp.first,u=tmp.second;
        if(dist[u]<d)   continue;
        for(pair<int,int>x:g[u])
        {
            if(d+x.second<dist[x.first])
            {
                dist[x.first]=dist[u]+x.second;
                pq.push({dist[x.first],x.first});
            }
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>m;
    for(int i=0;i<k;i++)    cin>>imv[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(int mask=0;mask<MASK(k);mask++)
    {
        for(int i=0;i<=n;i++)
        {
            dp[mask][i]=INF;
        }
    }
    for(int i=0;i<k;i++)    dp[MASK(i)][imv[i]]=0;
    for(int mask=1;mask<MASK(k);mask++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int submask=mask;submask>=0;submask=(submask-1)&mask)
            {
                dp[mask][i]=min(dp[mask][i],dp[mask^submask][i]+dp[submask][i]);
                if(submask==0)  break;
            }
        }
        dijsktra(dp[mask]);
    }
    cout<<dp[MASK(k)-1][imv[0]];
    return 0;
}

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