結果
問題 |
No.2387 Yokan Factory
|
ユーザー |
![]() |
提出日時 | 2023-07-21 21:43:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 705 ms / 5,000 ms |
コード長 | 1,595 bytes |
コンパイル時間 | 4,250 ms |
コンパイル使用メモリ | 265,704 KB |
最終ジャッジ日時 | 2025-02-15 16:41:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } ll dijk(int n, vector<vector<pair<int,ll>>> &ikeru){ const ll inf = (1e18) + 50; vector<ll> d(n, inf); d[0] = 0; priority_queue<pair<ll,int>> pq; pq.push(pair(0, 0)); while(!pq.empty()){ auto [tmp, i] = pq.top(); pq.pop(); tmp = -tmp; if (tmp > d[i]) continue; for (auto [j, dist] : ikeru[i]){ ll targ = dist + tmp; if (targ < d[j]){ d[j] = targ; pq.push(pair(-targ, j)); } } } return d[n-1]; } int main(){ int n, m; cin >> n >> m; ll x; cin >> x; //vector ikeru(n, vector<pair<int,ll>>(0)); vector<tuple<int,int,ll,ll>> edge; rep(i,0,m){ int u, v; cin >> u >> v; u--; v--; ll a, b; cin >> a >> b; edge.push_back(make_tuple(u, v, a, b)); } int lb = -1; int ub = 1e9 + 6; while (ub - lb > 1){ int targ = (lb + ub) / 2; vector ikeru(n, vector<pair<int,ll>>(0)); for (auto [u, v, a, b] : edge){ if (b >= targ){ ikeru[u].push_back(pair(v, a)); ikeru[v].push_back(pair(u, a)); } } //cout << dijk(n, ikeru) << " " << x << " " << targ << '\n'; if (dijk(n, ikeru) <= x){ lb = targ; }else{ ub = targ; } } cout << lb << '\n'; }