oj.uz

Submission #589237

# Submission time Handle Problem Language Result Execution time Memory
589237 2022-07-04T10:51:20 Z MohammadAghil Cities (BOI16_cities) C++17
100 / 100
 2854 ms 47164 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<ll, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 2e5 + 5, maxk = 5, lg = 35, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

vector<pp> adj[maxn];
int imp[maxk];
ll dp[maxn][1<<maxk];


int main(){ IOS();
     int n, k, m; cin >> n >> k >> m;
     rep(i,0,k) cin >> imp[i], imp[i]--;
     rep(i,0,m){
          int u, v, w; cin >> u >> v >> w; u--, v--;
          adj[u].pb({v, w}), adj[v].pb({u, w});
     }
     rep(msk,1,1<<k){
          priority_queue<pp, vector<pp>, greater<pp>> q;
          rep(i,0,n){
               dp[i][msk] = inf;
               rep(t,0,k) if(imp[t] == i && (msk>>t&1)) dp[i][msk] = dp[i][msk^(1<<t)];
               for(int j = msk&(msk-1); j; j = (j-1)&msk){
                    dp[i][msk] = min(dp[i][msk], dp[i][j] + dp[i][msk^j]);
               }
               q.push({dp[i][msk], i});
          }
          while(sz(q)){
               auto[w, r] = q.top(); q.pop();
               if(w != dp[r][msk]) continue;
               for(auto[u, d]: adj[r]) if(dp[u][msk] > w + d) q.push({dp[u][msk] = w + d, u});
          }
     }
     ll ans = inf;
     rep(i,0,n) ans = min(ans, dp[i][(1<<k)-1]);
     cout << ans << '\n';
     return 0;  
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 47056 KB Output is correct
2 Correct 663 ms 46592 KB Output is correct
3 Correct 434 ms 39248 KB Output is correct
4 Correct 64 ms 14476 KB Output is correct
5 Correct 355 ms 47088 KB Output is correct
6 Correct 60 ms 14380 KB Output is correct
7 Correct 7 ms 5460 KB Output is correct
8 Correct 5 ms 5372 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5492 KB Output is correct
2 Correct 8 ms 5460 KB Output is correct
3 Correct 7 ms 5332 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 47124 KB Output is correct
2 Correct 1380 ms 46608 KB Output is correct
3 Correct 895 ms 39260 KB Output is correct
4 Correct 758 ms 31976 KB Output is correct
5 Correct 171 ms 18096 KB Output is correct
6 Correct 64 ms 16576 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2854 ms 47160 KB Output is correct
2 Correct 2761 ms 47164 KB Output is correct
3 Correct 2774 ms 46764 KB Output is correct
4 Correct 1863 ms 39272 KB Output is correct
5 Correct 1477 ms 31904 KB Output is correct
6 Correct 279 ms 18204 KB Output is correct
7 Correct 79 ms 16848 KB Output is correct