結果
| 問題 | No.2387 Yokan Factory |
| ユーザー |
 hibit_at
|
| 提出日時 | 2023-07-21 22:17:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 801 ms / 5,000 ms |
| コード長 | 5,790 bytes |
| コンパイル時間 | 1,222 ms |
| コンパイル使用メモリ | 116,024 KB |
| 最終ジャッジ日時 | 2025-02-15 17:02:07 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <math.h>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <utility>#include <vector>#include <stack>#include <complex>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep1(i, n) for (int i = 1; i < n + 1; i++)#define rev(i, n) for (int i = n - 1; i >= 0; i--)#define all(A) A.begin(), A.end()#define itr(A, l, r) A.begin() + l, A.begin() + r#define debug(var) cout << #var << " = " << var << endl;typedef long long ll;template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "(" << p.first << "," << p.second << ")";return os;}template <typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p){is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v){for (int i = 0; i < (int)v.size(); i++){os << v[i] << (i + 1 != (int)v.size() ? " " : "");}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v){for (int i = 0; i < (int)v.size(); i++){os << v[i] << endl;}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v){for (int i = 0; i < (int)v.size(); i++){os << "i = " << i << endl;os << v[i];}return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v){for (T &in : v)is >> in;return is;}template <typename T, typename S>ostream &operator<<(ostream &os, map<T, S> &mp){for (auto &[key, val] : mp){os << key << ":" << val << " ";}cout << endl;return os;}template <typename T>ostream &operator<<(ostream &os, set<T> st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, multiset<T> st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, queue<T> q){while (q.size()){os << q.front() << " ";q.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, deque<T> q){while (q.size()){os << q.front() << " ";q.pop_front();}return os;}template <typename T>ostream &operator<<(ostream &os, stack<T> st){while (st.size()){os << st.top() << " ";st.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T> pq){while (pq.size()){os << pq.top() << " ";pq.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T, vector<T>, greater<T>> mpq){while (mpq.size()){os << mpq.top() << " ";mpq.pop();}return os;}int main(){ll n, m, x;cin >> n >> m >> x;using S = pair<pair<ll, ll>, ll>;vector<vector<S>> to(n, vector<S>());rep(i, m){ll u, v, a, b;cin >> u >> v >> a >> b;u--;v--;to[u].push_back({{a, b}, v});to[v].push_back({{a, b}, u});}// debug(to);ll ng = 1e18;ll ok = 0;while (abs(ng - ok) > 1){ll mid = ng + ok;mid /= 2;// debug(mid);priority_queue<S, vector<S>, greater<S>> q;q.push({{0, 0}, 0});vector<ll> dist(n, 1e18);while (q.size()){auto [info, now] = q.top();q.pop();// debug(now);auto [cost, width] = info;if (cost >= dist[now]){continue;}dist[now] = cost;for (auto [next_info, next] : to[now]){// debug(next);// debug(next_info);auto [next_cost, next_width] = next_info;if (next_width < mid){continue;}// debug(next_info);if (cost + next_cost >= dist[next]){continue;}q.push({{cost + next_cost, next_width}, next});}}// debug(dist);if (dist[n - 1] <= x){ok = mid;}else{ng = mid;}}// cout << ok << endl;priority_queue<S, vector<S>, greater<S>> q;q.push({{0, 0}, 0});vector<ll> dist(n, 1e18);while (q.size()){auto [info,now] = q.top();q.pop();// debug(now);auto [cost, width] = info;if (cost >= dist[now]){continue;}dist[now] = cost;for (auto [next_info, next] : to[now]){// debug(next);// debug(next_info);auto [next_cost, next_width] = next_info;if (next_width < ok){continue;}// debug(next_info);if (cost + next_cost >= dist[next]){continue;}q.push({{cost + next_cost, next_width}, next});}}// debug(dist);if (dist[n - 1] <= x){cout << ok << endl;}else{cout << -1 << endl;}}