oj.uz

Submission #226183

# Submission time Handle Problem Language Result Execution time Memory
226183 2020-04-22T18:21:49 Z MKopchev Cities (BOI16_cities) C++14
100 / 100
 3808 ms 46556 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42,kmax=5;

const long long inf=1e18;

int n,m,k;

vector< pair<int,int> > adj[nmax];

int special[kmax];

long long dp[1<<kmax][nmax];

priority_queue< pair<long long,int> > pq,idle;

int main()
{
    scanf("%i%i%i",&n,&k,&m);

    for(int i=0;i<k;i++)scanf("%i",&special[i]);

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%i%i%i",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    for(int i=0;i<(1<<k);i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=inf;

    for(int i=0;i<k;i++)
        dp[1<<i][special[i]]=0;

    for(int state=1;state<(1<<k);state++)
    {
        /*
        cout<<"time=1"<<endl;
        for(int node=1;node<=n;node++)
            cout<<state<<" "<<node<<" -> "<<dp[state][node]<<endl;
        */
        for(int submask=state;submask;submask=(submask-1)&state)
        {
            for(int node=1;node<=n;node++)
                dp[state][node]=min(dp[state][node],dp[submask][node]+dp[state^submask][node]);
        }
        /*
        cout<<"time=2"<<endl;
        for(int node=1;node<=n;node++)
            cout<<state<<" "<<node<<" -> "<<dp[state][node]<<endl;
        */
        pq=idle;
        for(int node=1;node<=n;node++)
        {
            pq.push({-dp[state][node],node});
            dp[state][node]=inf;
        }

        while(pq.size())
        {
            pair<long long,int> tp=pq.top();
            pq.pop();

            tp.first=-tp.first;

            //cout<<tp.first<<" "<<tp.second<<endl;

            if(dp[state][tp.second]<=tp.first)continue;

            dp[state][tp.second]=tp.first;

            for(auto k:adj[tp.second])
                pq.push({-(k.second+tp.first),k.first});
        }
        /*
        cout<<"time=3"<<endl;
        for(int node=1;node<=n;node++)
            cout<<state<<" "<<node<<" -> "<<dp[state][node]<<endl;
        */
    }

    long long output=inf;

    for(int node=1;node<=n;node++)
        output=min(output,dp[(1<<k)-1][node]);

    printf("%lld\n",output);
    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&k,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~~
cities.cpp:22:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<k;i++)scanf("%i",&special[i]);
                         ~~~~~^~~~~~~~~~~~~~~~~~
cities.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 27800 KB Output is correct
2 Correct 1010 ms 27484 KB Output is correct
3 Correct 433 ms 16384 KB Output is correct
4 Correct 625 ms 18928 KB Output is correct
5 Correct 501 ms 24664 KB Output is correct
6 Correct 330 ms 18916 KB Output is correct
7 Correct 11 ms 2944 KB Output is correct
8 Correct 9 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3072 KB Output is correct
2 Correct 16 ms 3072 KB Output is correct
3 Correct 11 ms 2944 KB Output is correct
4 Correct 14 ms 3072 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1918 ms 34012 KB Output is correct
2 Correct 1942 ms 33624 KB Output is correct
3 Correct 904 ms 22636 KB Output is correct
4 Correct 1568 ms 27356 KB Output is correct
5 Correct 1269 ms 20844 KB Output is correct
6 Correct 1219 ms 20728 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3743 ms 46516 KB Output is correct
2 Correct 3791 ms 46556 KB Output is correct
3 Correct 3808 ms 46048 KB Output is correct
4 Correct 1826 ms 35180 KB Output is correct
5 Correct 3044 ms 33636 KB Output is correct
6 Correct 2480 ms 22244 KB Output is correct
7 Correct 2413 ms 20964 KB Output is correct