제출 #1185419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185419		epicci23	Voting Cities (NOI22_votingcity)	C++20	45 / 100	1094 ms	4508 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[a].push_back({b, c});
  }	

  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;
    }

    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 mask = 0; mask < LOG; mask++){
      int cur = 0;
      for(int j = 0; j < 5; j++) if(mask >> j & 1) cur += pr[j];
      if(cur < dist[st][mask]){
        dist[st][mask] = cur;
        pq.push({cur, st, mask});
      }
    }

    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 ans = INF;
    for(int i = 0; i < n; i++){
      if(!mark[i]) continue;
      ans = min(ans, dist[i][0]);
    }
    
    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: 0 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 0 / 50