Submission #1272707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272707		huhuhuhuhu	Voting Cities (NOI22_votingcity)	C++20	100 / 100	330 ms	15260 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define pll pair<long long, long long>

template <int t>
using arr = array<long long, t>;

long long n, e, s;
vector<long long> cities;
vector<pll> rel[20005];

long long dist[5005][50];
long long q;

int main() {
  cin >> n >> e >> s;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < 32; j++) {
      dist[i][j] = 1e16;
    }
  }
  for (int i = 0; i < s; i++) {
    long long v;
    cin >> v;
    cities.push_back(v);
  }
  for (int i = 0; i < e; i++) {
    long long u, v, p;
    cin >> u >> v >> p;
    rel[v].push_back({u, p});
  }

  priority_queue<arr<3>, vector<arr<3>>, greater<arr<3>>> pq;
  for (auto &x : cities) {
    pq.push({0, x, 0});
  }

  while (!pq.empty()) {
    auto [price, pos, data] = pq.top();
    pq.pop();
    if (dist[pos][data] <= price) {
      continue;
    }
    // printf("ok %lld %lld %lld\n", pos, data, price);
    dist[pos][data] = price;
    for (auto &next : rel[pos]) {
      auto [nextPos, nextPrice] = next;
      pq.push({price + nextPrice, nextPos, data});
      for (int i = 0; i < 5; i++) {
        if ((data >> i) & 1) {
          continue;
        }
        long long newPrice = nextPrice * (10 - i - 1) / 10;
        pq.push({ newPrice + price, nextPos, data + (1 << i) });
      }
    }
  }

  cin >> q;
  while (q--) {
    long long pos;
    cin >> pos;

    arr<5> price;
    for (int i = 0; i < 5; i++) {
      cin >> price[i];
    }

    if (dist[pos][0] == 1e16) {
      // cout <<"noo" << endl;
      cout << -1 << endl;
      continue;
    }
    // cout << dist[pos][0] << endl;
    
    long long cPrice = 1e16;
    for (int i = 0; i < 32; i++) {
      bool good = true;
      long long curPrice = dist[pos][i];

      for (int idx = 0; idx < 5; idx++) {
        if ((i >> idx & 1) == 0) {
          continue;
        }
        if (price[idx] == -1) {
          good = false;
          break;
        }
        curPrice += price[idx];
      }
      if (!good) {
        continue;
      }
      cPrice = min(cPrice, curPrice);
    }
    
    
    cout << cPrice << endl;
  }

}

• 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