結果
問題 | 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;}