結果
問題 |
No.2387 Yokan Factory
|
ユーザー |
|
提出日時 | 2023-07-21 21:55:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 378 ms / 5,000 ms |
コード長 | 1,505 bytes |
コンパイル時間 | 1,952 ms |
コンパイル使用メモリ | 206,128 KB |
最終ジャッジ日時 | 2025-02-15 16:49:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> // #include "atcoder/modint" using i64 = long long; // using Fp = atcoder::modint998244353; constexpr i64 inf = 1ll << 60; struct Edge { int to; i64 cost; i64 width; }; int main() { int N, M; i64 X; std::cin >> N >> M >> X; std::vector<int> U(M), V(M); std::vector<i64> A(M), B(M); std::vector<std::vector<Edge>> graph(N); for (int i = 0; i < M; ++i) { std::cin >> U[i] >> V[i]; --U[i], --V[i]; std::cin >> A[i] >> B[i]; graph[U[i]].push_back({V[i], A[i], B[i]}); graph[V[i]].push_back({U[i], A[i], B[i]}); } i64 ok = -1, ng = 1ll << 60; auto calcDist = [&](i64 m) { std::vector<i64> dist(N, inf); dist[0] = 0; std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> pq; pq.push({0, 0}); while (not pq.empty()) { const auto [nd, f] = pq.top(); pq.pop(); if (nd > dist[f]) continue; for (const auto &[t, c, w] : graph[f]) { if (w < m) continue; if (dist[t] > dist[f] + c) { dist[t] = dist[f] + c; pq.push({dist[t], t}); } } } return dist[N - 1]; }; while (ng - ok > 1) { const auto mid = (ok + ng) / 2; if (calcDist(mid) <= X) ok = mid; else ng = mid; } std::cout << ok << std::endl; }