Submission #793498

#	Time	Username	Problem	Language	Result	Execution time	Memory
793498		asdfgrace	Toll (BOI17_toll)	C++17	100 / 100	2151 ms	7792 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
constexpr int INF = 1000000007; //998244353;

int k, n, m, q;
vector<vector<pair<int, int>>> edges;

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> k >> n >> m >> q;
  edges.resize(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