結果
問題 | No.2387 Yokan Factory |
ユーザー |
|
提出日時 | 2023-07-21 21:42:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 654 ms / 5,000 ms |
コード長 | 3,437 bytes |
コンパイル時間 | 6,055 ms |
コンパイル使用メモリ | 263,684 KB |
最終ジャッジ日時 | 2025-02-15 16:39:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;// typetypedef long long ll;typedef long double ld;using i128 = __int128_t;template<class T> using pq = priority_queue<T>;template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;template<class T> using v = vector<T>;#define V vector#define pl pair<ll, ll>#define vl v<ll>#define vp v<pl>#define vm v<mint>// IN-OUT#define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);ostream &operator<<(ostream &os, const i128 &v) {if(v == 0) { return (os << "0"); }i128 num = v;if(v < 0) { os << '-'; num = -num; }string s;for(; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }reverse(s.begin(), s.end());return (os << s);}void Yes(bool b=1) { cout << ( b == 1 ? "Yes" : "No" ) << "\n"; }void YES(bool b=1) { cout << ( b == 1 ? "YES" : "NO" ) << "\n"; }void No(bool b=1) { cout << ( b == 1 ? "No" : "Yes" ) << "\n"; }void NO(bool b=1) { cout << ( b == 1 ? "NO" : "YES" ) << "\n"; }void CIN() {}template <typename T, class... U> void CIN(T &t, U &...u) { cin >> t; CIN(u...); }void COUT() { cout << "\n"; }template <typename T, class... U, char sep = ' '> void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); }#define dump(x) cerr << #x << ":"<< x << "\n";#define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n";// macro#define bp __builtin_popcountll#define ALL(x) x.begin(),x.end()#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define reps(i, s, n) for (ll i = s; i < (ll)(n); i++)#define sz(x) (ll)x.size()ll xd[]={0, 1, 0, -1, 1, 1, -1, -1};ll yd[]={1, 0, -1, 0, 1, -1, -1, 1};// functiontemplate<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<typename T>int bl(T x) { int s = 0; while(x) {x >>= 1; s++;} return s; } // bitlengthll rmax(ll a, ll b){return max(a, b);}ll rmin(ll a, ll b){return min(a, b);}ll rsum(ll a, ll b){return a + b;}ll rzero(){return 0;}// constantlong double PI = 3.14159265358979;#define INF32 2147483647#define INF64 9223372036854775807#define INF 922337203685477580using mint = modint998244353;// using mint = modint1000000007;/* SOLVE BEGIN ************************************************************************** */void solve(){ll n, m, x;cin >> n >> m >> x;v<v<tuple<ll, ll, ll>>> edge(n);rep(i, m){ll a, b, c, d;CIN(a, b, c, d);a--; b--;edge[a].emplace_back(b, c, d);edge[b].emplace_back(a, c, d);}auto check = [&](ll wj){pqg<pl> Q;vl dist(n, INF), visit(n);dist[0] = 0;Q.emplace(0, 0);while(sz(Q)){auto [d, now] = Q.top(); Q.pop();if(now == n - 1) return true;if(visit[now]) continue;visit[now] = 1;for(auto [next, cost, w] : edge[now]){if(w < wj) continue;if(dist[now] + cost > x) continue;if(visit[next]) continue;if(chmin(dist[next], dist[now] + cost)) Q.emplace(dist[next], next);}}return false;};ll ok = -1, ng = INF;while(ng - ok > 1){ll wj = (ok + ng) / 2;if(check(wj)) ok = wj;else ng = wj;}cout << ok << "\n";}int main(){NYANsolve();return 0;}