Submission #1245766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245766		hoangnoobpro	Cities (BOI16_cities)	C++20	100 / 100	1319 ms	49596 KiB

cities

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define nmax 200007
#define fi first
#define se second
#define ll int
ll t=1,n,m,i,j,d=0,x=0,k=0,y,a[nmax];
long long dp[nmax][34],z;
bool f[nmax][34];
priority_queue<pair<long long,ll>,vector<pair<long long,ll>>,greater<pair<long long,ll>>>pq;
vector<pair<ll,long long>>v[nmax];
vector<ll>luu[37];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    for(i=1;i<=n;++i)
    {
        for(j=0;j<32;++j)
        {
            dp[i][j]=1e17;
        }
    }
    for(i=1;i<=k;++i)
    {
        cin>>a[i];
        dp[a[i]][1<<(i-1)]=0;
    }
    for(i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(i=1;i<(1<<k);++i)
    {
        for(j=i+1;j<(1<<k);++j)
            if((j^i)==j-i)
        {
            luu[j].push_back(i);
        }
    }
    for(int y=1;y<(1<<k);++y)
    {
        for(int i=1; i<=n; ++i)
        {
            for(z=y;z;z=(z-1)&y)
            {
                dp[i][y]=min(dp[i][y],dp[i][z]+dp[i][z^y]);
            }
            pq.push({dp[i][y],i});
        }
        while(pq.size()>0)
        {
            z=pq.top().fi;
            x=pq.top().se;
            pq.pop();
            if(f[x][y])continue;
            f[x][y]=1;
            for(pair<ll,ll>i:v[x])
            {
                if(dp[i.fi][y]>dp[x][y]+i.se)
                {
                    dp[i.fi][y]=dp[x][y]+i.se;
                    pq.push({dp[i.fi][y],i.fi});
                }
            }
        }
    }
    z=1e18;
    for(i=1;i<=n;++i)
    {
        z=min(z,dp[i][(1<<k)-1]);
    }
    cout<<z;
}

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