結果
| 問題 | No.2387 Yokan Factory |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-16 02:21:12 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,054 bytes |
| 記録 | |
| コンパイル時間 | 2,270 ms |
| コンパイル使用メモリ | 211,760 KB |
| 実行使用メモリ | 13,532 KB |
| 最終ジャッジ日時 | 2026-11-16 02:21:22 |
| 合計ジャッジ時間 | 10,356 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 WA * 3 |
ソースコード
#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<algorithm>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using tu = tuple<ll, ll, ll>;
int main(void){
ll n, m, x; cin >> n >> m >> x;
vector<vector<tu>> to(n);
for(int i=0; i<m; i++){
int u, v; ll a, b; cin >> u >> v >> a >> b; u--, v--;
to[u].emplace_back(v, a, b); swap(u, v);
to[u].emplace_back(v, a, b);
}
auto judge=[&](int tar){
vector<ll> dist(n, 1e18);
dist[0]=0;
priority_queue<P, vector<P>, greater<P>> pri;
pri.emplace(0, 0);
while(pri.size()){
auto [d, id]=pri.top(); pri.pop();
if(dist[id]!=d) continue;
for(auto [v, a, b]:to[id]){
if(b<tar) continue;
ll nd=d+a;
if(dist[v]>nd){
dist[v]=nd;
pri.emplace(nd, v);
}
}
}
return dist[n-1]<=x;
};
int left=-1, right=1e9+1;
while(right-left>1){
int mid=(left+right)/2;
if(judge(mid)) left=mid;
else right=mid;
}
cout << left << endl;
return 0;
}