oj.uz

Submission #589225

# Submission time Handle Problem Language Result Execution time Memory
589225 2022-07-04T10:45:34 Z MohammadAghil Cities (BOI16_cities) C++17
100 / 100
 3850 ms 51332 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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 4 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 892 ms 51332 KB Output is correct
2 Correct 763 ms 50740 KB Output is correct
3 Correct 488 ms 41164 KB Output is correct
4 Correct 83 ms 17804 KB Output is correct
5 Correct 377 ms 51232 KB Output is correct
6 Correct 70 ms 17720 KB Output is correct
7 Correct 6 ms 5460 KB Output is correct
8 Correct 5 ms 5428 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 51316 KB Output is correct
2 Correct 1543 ms 50640 KB Output is correct
3 Correct 1123 ms 41236 KB Output is correct
4 Correct 1000 ms 35896 KB Output is correct
5 Correct 239 ms 21988 KB Output is correct
6 Correct 123 ms 19904 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3850 ms 51160 KB Output is correct
2 Correct 3741 ms 51252 KB Output is correct
3 Correct 3584 ms 50852 KB Output is correct
4 Correct 2441 ms 41152 KB Output is correct
5 Correct 2216 ms 35996 KB Output is correct
6 Correct 435 ms 21936 KB Output is correct
7 Correct 219 ms 20156 KB Output is correct