Submission #589237

#	Time	Username	Problem	Language	Result	Execution time	Memory
589237		MohammadAghil	Cities (BOI16_cities)	C++17	100 / 100	2854 ms	47164 KiB

cities

      #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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26