oj.uz

Submission #589229

# Submission time Handle Problem Language Result Execution time Memory
589229 2022-07-04T10:48:03 Z MohammadAghil Cities (BOI16_cities) C++17
100 / 100
 3533 ms 47032 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(auto[u, w]: adj[i]){
                    for(int j = msk&(msk-1); j; j = (j-1)&msk){
                         dp[i][msk] = min(dp[i][msk], dp[u][j] + w + 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5016 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 46980 KB Output is correct
2 Correct 788 ms 46444 KB Output is correct
3 Correct 460 ms 38944 KB Output is correct
4 Correct 73 ms 14276 KB Output is correct
5 Correct 347 ms 46892 KB Output is correct
6 Correct 63 ms 14376 KB Output is correct
7 Correct 5 ms 5452 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 8 ms 5456 KB Output is correct
3 Correct 6 ms 5380 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1642 ms 47004 KB Output is correct
2 Correct 1552 ms 46548 KB Output is correct
3 Correct 1089 ms 38940 KB Output is correct
4 Correct 982 ms 31816 KB Output is correct
5 Correct 225 ms 18036 KB Output is correct
6 Correct 102 ms 16468 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3457 ms 46992 KB Output is correct
2 Correct 3533 ms 47032 KB Output is correct
3 Correct 3351 ms 46484 KB Output is correct
4 Correct 2293 ms 39016 KB Output is correct
5 Correct 2032 ms 31872 KB Output is correct
6 Correct 437 ms 18156 KB Output is correct
7 Correct 213 ms 16716 KB Output is correct