oj.uz

Submission #897852

# Submission time Handle Problem Language Result Execution time Memory
897852 2024-01-03T20:57:02 Z maxFedorchuk Cities (BOI16_cities) C++17
100 / 100
 1688 ms 51320 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 5 ms 28412 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 34352 KB Output is correct
2 Correct 387 ms 34344 KB Output is correct
3 Correct 304 ms 23204 KB Output is correct
4 Correct 47 ms 22524 KB Output is correct
5 Correct 232 ms 29456 KB Output is correct
6 Correct 43 ms 20316 KB Output is correct
7 Correct 4 ms 10076 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18268 KB Output is correct
2 Correct 6 ms 18180 KB Output is correct
3 Correct 5 ms 18268 KB Output is correct
4 Correct 6 ms 18164 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 39368 KB Output is correct
2 Correct 800 ms 40208 KB Output is correct
3 Correct 488 ms 29364 KB Output is correct
4 Correct 428 ms 36708 KB Output is correct
5 Correct 128 ms 32532 KB Output is correct
6 Correct 51 ms 32844 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 50080 KB Output is correct
2 Correct 1688 ms 51320 KB Output is correct
3 Correct 1508 ms 49892 KB Output is correct
4 Correct 996 ms 39844 KB Output is correct
5 Correct 803 ms 46984 KB Output is correct
6 Correct 194 ms 42892 KB Output is correct
7 Correct 60 ms 43392 KB Output is correct