K-ésimo Caminho

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
const int OO = 2000000001;
const int MAX = 10000 * 110;

int n, m, q, U, V;
set<ii> path_edge;
vector<array<int, 3>> edges;
vector<ii> G[MAX];
int dist[MAX];

void mount(int k) {
   for(auto &[u, v, w] : edges) {
      for(int j = 0; j <= k; j++) {
         int a = u * (k + 1) + j, b = v * (k + 1) + j + 1;
         if(path_edge.count({u, v})) b--;
         if(b > v * (k + 1) + k) b = v * (k + 1) + k;
         G[a].push_back({b, w});
      }
   }
}

void dijkstra(int k) {
   for(int i = 0; i <= n * (k + 1) + k; i++)
      dist[i] = OO;
   dist[U * (k + 1)] = 0;
   priority_queue<ii> pq;
   pq.push({0, U * (k + 1)});
   while(!pq.empty()) {
      int u = pq.top().second;
      int d = -pq.top().first;
      pq.pop();
      if(d > dist[u]) continue;
      for(auto &[v, w] : G[u])
         if(dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            pq.push({-dist[v], v});
         }
   }
}

int32_t main() {
   ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

   cin >> n >> m >> q >> U >> V; U--; V--;

   int cur, last = -1;
   while(cin >> cur) {
      cur--;
      if(last != -1) {
         // edge: last->cur
         path_edge.insert({last, cur});
      }
      if(cur == V) break;
      last = cur;
   }

   int sp_cost = 0;

   for(int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w; u--; v--;
      edges.push_back({u, v, w});
      if(path_edge.count({u, v})) sp_cost += w;
   }

   mount(101);
   dijkstra(101);

   while(q--) {
      int k, d;
      cin >> k >> d;
      bool fl = false;
      for(int j = k; j <= 102 and !fl; j++)
         if( abs(dist[ V * 102 + j ] - sp_cost) <= d)
            fl = true;
      if(fl) cout << "SIM\n";
      else cout << "NAO\n";
   }

    return 0;
}