Submission #1185426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185426		epicci23	Voting Cities (NOI22_votingcity)	C++20	100 / 100	67 ms	8376 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int) a.size()
using namespace std;

const int N = 5005;
const int INF = 1e18;
const int LOG = 32;

int n, m, k, mark[N];
vector<array<int,2>> v[N];

void _(){
  cin >> n >> m >> k;
  
  for(int i = 0; i < k; i++){
  	int a; cin >> a;
  	mark[a] = 1;
  }

  for(int i = 0; i < m; i++){
  	int a,b,c;
  	cin >> a >> b >> c;
  	v[b].push_back({a, c});
  }	

  array<int,LOG> dist[n+5];
  for(int i=0;i<n;i++) for(int j=0;j<LOG;j++) dist[i][j] = INF;
  priority_queue<array<int,3>,vector<array<int,3>>,greater<>> pq;
  
  for(int i = 0; i < n; i++){
  	if(mark[i]){
  	  dist[i][0] = 0;
  	  pq.push({0, i, 0});
  	}
  }

  while(!pq.empty()){

      int c = pq.top()[1];
      int d = pq.top()[0];
      int mask = pq.top()[2];
      pq.pop();
      if(d > dist[c][mask]) continue;

      for(auto [u, w] : v[c]){
        if(d + w < dist[u][mask]){
          dist[u][mask] = d + w;
          pq.push({d + w, u, mask});
        }
      }

      for(int i = 0; i < 5; i++){
        if(mask>>i&1) continue;
        for(auto [u, w] : v[c]){
          if(w - (i + 1) * (w / 10) + d < dist[u][mask ^ (1 << i)]){
            dist[u][mask ^ (1 << i)] = w - (i + 1) * (w / 10) + d;
            pq.push({w - (i + 1) * (w / 10) + d, u, mask ^ (1 << i)});
          }
        }
      }
  }

  int q;
  cin >> q;
  while(q--){

  	int st,pr[5];
    cin >> st;

    for(int i = 0; i < 5; i++){
      cin >> pr[i];
      if(pr[i] == -1) pr[i] = INF;
    }

    int ans = INF;
    for(int i = 0; i < LOG; i++){
      int cur = dist[st][i];
      for(int j = 0; j < 5; j++) if(i>>j&1) cur += pr[j];
      ans = min(ans, cur);
    }
    
    if(ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50