Submission #897852

#	Time	Username	Problem	Language	Result	Execution time	Memory
897852		maxFedorchuk	Cities (BOI16_cities)	C++17	100 / 100	1688 ms	51320 KiB

cities

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

const long long MXN=1e5+10;
const long long INF=1e18;

vector < pair < long long , long long > > mas[MXN];

long long dp[(1<<5)][MXN];
long long vis[MXN];
long long g[5];

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,k,m;
    cin>>n>>k>>m;

    for(long long i=0;i<k;i++)
    {
        cin>>g[i];
    }

    long long a,b,c;
    for(long long i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        mas[a].push_back({b,c});
        mas[b].push_back({a,c});
    }


    long long fn_msk=(1<<k);

    for(long long msk=1;msk<fn_msk;msk++)
    {
        for(long long i=1;i<=n;i++)
        {
            dp[msk][i]=INF;
        }
    }

    for(long long st=0;st<k;st++)
    {
        dp[(1<<st)][g[st]]=0;
    }

    for(long long msk=1;msk<fn_msk;msk++)
    {
        for(long long st=0;st<k;st++)
        {
            if((msk>>st)&1)
            {
                for(long long i=1;i<=n;i++)
                {
                    dp[msk][i]=min(dp[msk][i],dp[msk^(1<<st)][i]+dp[(1<<st)][i]);
                }
            }
        }


        priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > q;

        for(long long i=1;i<=n;i++)
        {
            q.push({dp[msk][i],i});
            vis[i]=0;
        }

        while(!q.empty())
        {
            long long zar=q.top().second;
            q.pop();

            if(vis[zar])
            {
                continue;
            }

            vis[zar]=1;

            for(auto [u,v]:mas[zar])
            {
                if(dp[msk][u]>(dp[msk][zar]+v))
                {
                    dp[msk][u]=dp[msk][zar]+v;
                    q.push({dp[msk][u],u});
                }
            }
        }
    }

    long long res=INF;
    for(long long i=1;i<=n;i++)
    {
        res=min(res,dp[fn_msk-1][i]);
    }

    cout<<res<<"\n";
    return 0;
}

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