Submission #1245759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245759		hoangnoobpro	Cities (BOI16_cities)	C++20	14 / 100	665 ms	93772 KiB

cities

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define nmax 1000007
#define fi first
#define se second
#define ll long long
ll t=1,n,m,i,j,d=0,x=0,k=0,y,z,a[nmax],f[nmax][34],dp[nmax][34];
priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>>pq;
vector<pair<ll,ll>>v[nmax];
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;
        pq.push({0,{a[i],1<<(i-1)}});
    }
    for(i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    while(pq.size()>0)
    {
        z=pq.top().fi;
        x=pq.top().se.fi;
        y=pq.top().se.se;
        pq.pop();
        if(f[x][y])continue;
        f[x][y]=1;
        for(i=1;i<y;++i)
        {
            if((y^i)==(y-i))
            {
                j=(y^i);
                dp[x][y]=min(dp[x][y],dp[x][i]+dp[x][j]);
            }
        }
        for(i=y+1;i<(1<<k);++i)
        {
            if((i^y)==(i-y))
            {
                j=i-y;
                dp[x][i]=min(dp[x][i],dp[x][y]+dp[x][j]);
            }
        }
        for(pair<ll,ll>i:v[x])
        {
            for(j=1;j<=y;++j)
                if((y^j)==(y-j))
            {
                if(dp[i.fi][j]>dp[x][j]+i.se)
                {
                    dp[i.fi][j]=dp[x][j]+i.se;
                    pq.push({dp[i.fi][j],{i.fi,j}});
                }
            }
        }
    }
    x=1e18;
    for(i=1;i<=n;++i)
    {
        x=min(x,dp[i][(1<<k)-1]);
    }
    cout<<x;
}

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