結果
問題 | No.2387 Yokan Factory |
ユーザー |
|
提出日時 | 2023-07-21 21:56:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 378 ms / 5,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 2,154 ms |
コンパイル使用メモリ | 204,916 KB |
最終ジャッジ日時 | 2025-02-15 16:50:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Edge{int to;long long cost;long long cap;};using Graph = vector<vector<Edge>>;using Pair = pair<long long, int>;void Dijkstra(const Graph& graph, vector<long long>& distances, int startIndex, int cap){priority_queue<Pair, vector<Pair>, greater<Pair>> q;q.emplace((distances[startIndex] = 0), startIndex);while (!q.empty()){const long long distance = q.top().first;const int from = q.top().second;q.pop();if (distances[from] < distance)continue;for (const auto& edge : graph[from]){const long long d = (distances[from] + edge.cost);if (d < distances[edge.to] and edge.cap >= cap){q.emplace((distances[edge.to] = d), edge.to);}}}}int main() {int N, M;long long X;cin >> N >> M >> X;Graph G(N);for (int i = 0; i < M; i++){int u, v, a, b;cin >> u >> v >> a >> b;u--;v--;G[u].push_back({v, a, b});G[v].push_back({u, a, b});}int l = -1, r = 1e9 + 10;while (r - l > 1){int mid = l + (r - l) / 2;vector<long long> d(N, (long long) 1e15);Dijkstra(G, d, 0, mid);if (d[N - 1] <= X){l = mid;} else {r = mid;}}cout << l << '\n';}