Submission #226183

#	Time	Username	Problem	Language	Result	Execution time	Memory
226183		MKopchev	Cities (BOI16_cities)	C++14	100 / 100	3808 ms	46556 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26