oj.uz

Submission #361575

# Submission time Handle Problem Language Result Execution time Memory
361575 2021-01-30T15:33:50 Z Dymo Cities (BOI16_cities) C++14
100 / 100
 5473 ms 150164 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 58944 KB Output is correct
2 Correct 883 ms 59728 KB Output is correct
3 Correct 333 ms 52564 KB Output is correct
4 Correct 82 ms 14484 KB Output is correct
5 Correct 463 ms 52896 KB Output is correct
6 Correct 77 ms 14296 KB Output is correct
7 Correct 7 ms 5740 KB Output is correct
8 Correct 5 ms 5612 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5936 KB Output is correct
2 Correct 10 ms 5936 KB Output is correct
3 Correct 8 ms 5936 KB Output is correct
4 Correct 8 ms 5612 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2470 ms 96052 KB Output is correct
2 Correct 2016 ms 96616 KB Output is correct
3 Correct 1482 ms 64852 KB Output is correct
4 Correct 1218 ms 56744 KB Output is correct
5 Correct 225 ms 23764 KB Output is correct
6 Correct 87 ms 17220 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5473 ms 145464 KB Output is correct
2 Correct 5457 ms 149512 KB Output is correct
3 Correct 4879 ms 150164 KB Output is correct
4 Correct 2970 ms 140912 KB Output is correct
5 Correct 3058 ms 85440 KB Output is correct
6 Correct 524 ms 33868 KB Output is correct
7 Correct 113 ms 20736 KB Output is correct