제출 #931368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931368		vjudge1	Voting Cities (NOI22_votingcity)	C++17	100 / 100	580 ms	52196 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define tp3 tuple<int, int, int>
#define all(x) x.begin(), x.end()

const int N = 5e3+3, M = 32, inf = 1e18;

int n, e, k, q, a[N], dis[M][M][N];
vector<pair<int, int>> adj[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      for (int ij = 0; ij < N; ij++) {
        dis[i][j][ij] = inf;
      }
    }
  }

  cin >> n >> e >> k;
  for (int i = 0; i < k; i++) {
    int x;
    cin >> x;
    a[i] = x;
  }
  for (int i = 0; i < e; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    adj[y].push_back(make_pair(x, z));
  }

  for (int mask = 0; mask < M; mask++) {
    priority_queue<tp3> pq;
    for (int i = 0; i < k; i++) {
      pq.push(make_tuple(-0, mask, a[i]));
    }
  
    while (!pq.empty()) {
      int d = -get<0>(pq.top());
      int nwMask = get<1>(pq.top());
      int x = get<2>(pq.top());
      pq.pop();

      if (dis[mask][nwMask][x] <= d) continue;
      dis[mask][nwMask][x] = d;//cerr << x << " " << d << " " << nwMask << " " << mask << endl;

      for (auto& [y, z] : adj[x]) {
        for (int i = 0; i < 5; i++) {
          // uso el ticket i
          if (!((nwMask >> i) & 1) || dis[mask][nwMask][y] <= d + z * (10-i-1)/10) continue;
          pq.push(make_tuple(-(d + (z*(10-i-1)) / 10), nwMask ^ (1 << i), y)); 
        }

        if (dis[mask][nwMask][y] <= d+z) continue;
        pq.push(make_tuple(-(d+z), nwMask, y)); 
      }
    }
  }

  cin >> q;
  while (q--) {
    int s, p[5];
    cin >> s;
    for (int i = 0; i < 5; i++) {
      cin >> p[i];
    }

    int ans = inf;
    for (int mask = 0; mask < M; mask++) {
      int sum = 0;
      bool ok = 1;
      for (int i = 0; i < 5; i++) {
        if ((mask >> i) & 1) {
          if (p[i] == -1) ok = 0;
          sum += p[i];
        }
      }
//if (dis[mask][0][s] < inf && ok) cerr << sum << " " << mask << " " << dis[mask][0][s] << " " << dis[mask][0][s] + sum << endl;
      if (ok) ans = min(ans, dis[mask][0][s] + sum);
    }
    cout << (ans == inf ? -1 : ans) << "\n";
  }
}

• 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