제출 #963723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963723		Soumya1	치료 계획 (JOI20_treatment)	C++17	35 / 100	3021 ms	5968 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
void testCase() {
  int n, m;
  cin >> n >> m;
  vector<int> t(m), l(m), r(m), c(m);
  for (int i = 0; i < m; i++) cin >> t[i] >> l[i] >> r[i] >> c[i];
  priority_queue<pair<ll, int>> pq;
  vector<bool> vis(m);
  vector<ll> dist(m, inf);
  for (int i = 0; i < m; i++) {
    if (l[i] == 1) {
      dist[i] = c[i];
      pq.push({-dist[i], i});
    }
  }
  while (!pq.empty()) {
    auto [_, u] = pq.top();
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = 0; i < m; i++) {
      if (t[i] < t[u]) {
        if (r[u] >= l[i] + t[u] - t[i] - 1 && dist[i] > dist[u] + c[i]) {
          dist[i] = dist[u] + c[i];
          pq.push({-dist[i], i});
        }
      } else {
        if (l[i] <= r[u] - t[i] + t[u] + 1 && dist[i] > dist[u] + c[i]) {
          dist[i] = dist[u] + c[i];
          pq.push({-dist[i], i});
        }
      }
    }
  }
  ll ans = inf;
  for (int i = 0; i < m; i++) {
    if (r[i] == n) ans = min(ans, dist[i]);
  }
  cout << (ans == inf ? -1 : ans) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61