結果
問題 | No.2387 Yokan Factory |
ユーザー |
|
提出日時 | 2023-07-21 21:37:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 368 ms / 5,000 ms |
コード長 | 4,178 bytes |
コンパイル時間 | 3,129 ms |
コンパイル使用メモリ | 312,888 KB |
最終ジャッジ日時 | 2025-02-15 16:33:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#if !__INCLUDE_LEVEL__#include __FILE__const ll INF = numeric_limits<long long>::max()/3;void solve(){ll N, M, X; cin >> N >> M >> X;vvc<tuple<ll, ll, ll>> graph(N);rep(i, M){ll a, b, c, d; cin >> a >> b >> c >> d;a--; b--;graph[a].eb(b, c, d);graph[b].eb(a, c, d);}auto dijkstra = [&](ll s, ll b){priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;vc<ll> dists(N, INF);dists[s] = 0;que.emplace(dists[s], 0);while(!que.empty()) {ll cost, v;tie(cost, v) = que.top();que.pop();if(dists[v] < cost) continue;for(auto [nv, ncost, nb] : graph[v]) {if(nb < b) continue;auto next_cost = cost + ncost;if(dists[nv] <= next_cost) continue;dists[nv] = next_cost;que.emplace(dists[nv], nv);}}return dists[N-1];};ll d = dijkstra(0, 0);if(d > X){print(-1);return;}ll l=0, r=INF;while(l+1<r){ll b = (l+r)/2;d = dijkstra(0, b);if(d<=X) l = b;else r = b;}print(l);}int main () {ios::sync_with_stdio(false);cin.tie(0);solve();}#else// #pragma region Macros#include<bits/stdc++.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cfenv>#include <cfloat>#include <chrono>#include <cinttypes>#include <climits>#include <cmath>#include <complex>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <immintrin.h>#include <initializer_list>#include <iomanip>#include <ios>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <streambuf>#include <string>#include <tuple>#include <type_traits>#include <typeinfo>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define ll long long#define OVERLOAD(e1,e2,e3,e4,NAME,...) NAME#define _rep1(i,n) for(long long i=0;i<n;i++)#define _rep2(i, a, b) for(long long i = a; i < b; ++i)#define _rep3(i, a, b, t) for(long long i = a; i* (t/abs(t)) < b * (t/abs(t)); i+=t)#define rep(...) OVERLOAD(__VA_ARGS__,_rep3,_rep2,_rep1,_)(__VA_ARGS__)#define all(x) (x).begin(),(x).end()#define sz(x) (ll)x.size()#define chmin(k,m) k = min(k,m)#define chmax(k,m) k = max(k,m)#define fi first#define se second#define pb push_back#define eb emplace_back#define mp make_pair#define pcnt __builtin_popcountll#define SORT(v) sort(all(v))#define UNIQUE(v) SORT(v);v.erase( unique(v.begin(), v.end()), v.end() );#define COPY(A, B) copy(all(A), B.begin());#define REV(v) reverse(all(v))#define MAX(x) *max_element(all(x))#define MIN(x) *min_element(all(x))#ifdef LOCAL#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl#else#define dbg(x) true#endifusing namespace std;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vc<T>>;template <typename T> using vvvc = vector<vvc<T>>;template <typename T> inline void print(const vector<T>& v, string s = " "){for(ll i=0; i<(ll)v.size(); i++) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}template <typename T, typename S> inline void print(const pair<T, S>& p){cout << p.first << " " << p.second << endl;}template <typename T> inline void print(const T& x) {cout << x << "\n";}template <typename T, typename S> inline void print(const vector<pair<T, S>>& v){for (auto&& p : v) print(p);}void yes(bool a){cout<<(a?"yes":"no")<<endl;}void YES(bool a){cout<<(a?"YES":"NO")<<endl;}void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}template <typename T> T SUM(vc<T> As){T ret=0; for(T a: As) ret += a; return ret;}// #pragma endregion#endif