Submission #793501

#	Time	Username	Problem	Language	Result	Execution time	Memory
793501		asdfgrace	Toll (BOI17_toll)	C++17	100 / 100	2213 ms	4480 KiB

toll

#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1000000007; //998244353;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int k, n, m, q;
  cin >> k >> n >> m >> q;
  vector<vector<pair<int, int>>> edges(n);
  for (int i = 0; i < m; ++i) {
    int a, b, w;
    cin >> a >> b >> w;
    edges[a].push_back({b, w});
  }
  vector<int> best(n, INF);
  while (q--) {
    int a, b;
    cin >> a >> b;
    fill(best.begin() + a, best.begin() + b + 1, INF);
    best[a] = 0;
    for (int i = a; i < b; ++i) {
      for (auto [next, wt] : edges[i]) {
        best[next] = min(best[next], best[i] + wt);
      }
    }
    if (best[b] == INF) cout << -1 << '\n';
    else cout << best[b] << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44