結果
問題 | No.2387 Yokan Factory |
ユーザー |
|
提出日時 | 2023-07-21 21:51:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 429 ms / 5,000 ms |
コード長 | 2,476 bytes |
コンパイル時間 | 2,042 ms |
コンパイル使用メモリ | 179,544 KB |
実行使用メモリ | 13,312 KB |
最終ジャッジ日時 | 2024-09-21 23:19:25 |
合計ジャッジ時間 | 6,092 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using pll = pair<ll, ll>;#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)#define rep(i, n) drep(i, 0, n - 1)#define all(a) (a).begin(), (a).end()#define pb push_back#define fi first#define se secondmt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());const ll MOD1000000007 = 1000000007;const ll MOD998244353 = 998244353;const ll MOD[3] = {999727999, 1070777777, 1000000007};const ll LINF = 1LL << 60;const int IINF = (1 << 30) - 1;template<typename T>struct Edge{int to;T w;T b;Edge(int to_, T w_, T b_){to = to_;w=w_;b=b_;}};template<typename T> using Tree = vector<vector<Edge<T>>>;template<typename T> using Graph = vector<vector<Edge<T>>>;int main(){cin.tie(nullptr);ios::sync_with_stdio(false);ll n, m, x; cin >> n >> m >> x;Graph<ll> G(n);rep(i, m){ll u, v, a, b; cin >> u >> v >> a >> b;u--; v--;G[u].pb(Edge<ll>(v, a, b));G[v].pb(Edge<ll>(u, a, b));}//輸送可能チェック{vector<ll> dist(n, LINF);dist[0] = 0;priority_queue<pll, vector<pll>, greater<pll>> PQ;PQ.push({0, 0});while(!PQ.empty()){ll v = PQ.top().se;ll tmp = PQ.top().fi;PQ.pop();if(dist[v] < tmp) continue;for(Edge<ll> e : G[v]){if(dist[v]+e.w < dist[e.to]){dist[e.to] = dist[v] + e.w;PQ.push({dist[e.to], e.to});}}}if(dist[n-1]>x){cout << -1 << endl;return 0;}}ll low = 0;ll high = 1e9+1;ll mid;while(high-low>1){mid = (low + high)/2;vector<ll> dist(n, LINF);dist[0] = 0;priority_queue<pll, vector<pll>, greater<pll>> PQ;PQ.push({0, 0});while(!PQ.empty()){ll v = PQ.top().se;ll tmp = PQ.top().fi;PQ.pop();if(dist[v] < tmp) continue;for(Edge<ll> e : G[v]){if(dist[v]+e.w<dist[e.to] && mid<=e.b){dist[e.to] = dist[v] + e.w;PQ.push({dist[e.to], e.to});}}}if(dist[n-1]<=x) low = mid;else high = mid;}cout << low << endl;}