Submission #361575

#	Time	Username	Problem	Language	Result	Execution time	Memory
361575		Dymo	Cities (BOI16_cities)	C++14	100 / 100	5473 ms	150164 KiB

cities

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

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =2e5+10;
const ll mod=1e9+7;
const ll base=3e16;
ll dp[maxn][6];
ll pos[maxn];
ll dp1[maxn][(1ll<<5)];
vector<pll> adj[maxn];
ll n;
ll k, m;
ll a[maxn];

void dosth(ll u,ll pos)
{
   for (int i=1;i<=n;i++)
   {
       dp[i][pos]=base;
   }
   dp[u][pos]=0;
   priority_queue<pll,vector<pll>,greater<pll>> q;
   q.push(make_pair(dp[u][pos],u));
   while (!q.empty())
   {
       auto p=q.top();
       q.pop();
       ll u=p.ss;
       if (p.ff!=dp[u][pos]) continue;
       for (auto t:adj[u])
       {
           ll to=t.ff;
           ll w=t.ss;
           if (dp[to][pos]>dp[u][pos]+w)
           {
               dp[to][pos]=dp[u][pos]+w;
               q.push(make_pair(dp[to][pos],to));
           }
       }
   }
}
ll dosth1()
{
    priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>> q;
   for (int i=1;i<=n;i++)
   {
       for (int j=1;j<(1ll<<k);j++)
       {
           dp1[i][j]=base;
       }
       q.push(make_pair(dp1[i][0],make_pair(i,0)));
   }
   while (!q.empty())
   {
       auto p=q.top();
       q.pop();
       ll u=p.ss.ff;
       ll t=p.ss.ss;
       if (dp1[u][t]!=p.ff) continue;
       if(t==(1ll<<k)-1)
       {
           return p.ff;
       }
       for (int j=0;j<k;j++)
       {
           if (t&(1ll<<j))
           {

           }
           else
           {
               ll w=dp[u][j];
               if (dp1[u][t^(1ll<<j)]>dp1[u][t]+w)
               {
                  dp1[u][t^(1ll<<j)]=dp1[u][t]+w;
                  q.push(make_pair(dp1[u][t^(1ll<<j)],make_pair(u,t^(1ll<<j))));
               }
           }
       }
       for (auto p:adj[u])
       {
           ll to=p.ff;
           ll w=p.ss;
           if (dp1[to][t]>dp1[u][t]+w)
           {
               dp1[to][t]=dp1[u][t]+w;
               q.push(make_pair(dp1[to][t],make_pair(to,t)));
           }
       }
   }
   ll ans=base;
   for (int i=1;i<=n;i++)
   {
       ans=min(ans,dp1[i][(1ll<<k)-1]);
   }
   return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
   cin>> n>> k>>m ;
   for (int i=0;i<k;i++)
   {
       cin>>a[i];

   }
   for (int i=1;i<=m;i++)
   {
       ll x, y, w;
        cin>> x>> y>> w;
        adj[x].pb(make_pair(y,w));
        adj[y].pb(make_pair(x,w));
   }
   for (int i=0;i<k;i++)
   {
       dosth(a[i],i);
   }
   cout <<dosth1();



}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  112 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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