結果
| 問題 | No.2387 Yokan Factory |
| ユーザー |
 Yuto Tokunaga
|
| 提出日時 | 2023-07-21 23:05:49 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,202 bytes |
| コンパイル時間 | 878 ms |
| コンパイル使用メモリ | 84,804 KB |
| 実行使用メモリ | 19,136 KB |
| 最終ジャッジ日時 | 2024-09-22 00:35:48 |
| 合計ジャッジ時間 | 13,422 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
コンパイルメッセージ
main.cpp: In function 'bool check(int)':
main.cpp:26:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
26 | for(auto &[u, a, b] : G[v]) {
| ^
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;
using P = pair<int,int>;
using T = tuple<int,int,int>;
const int INF = 1e9;
int N, M, X;
vector<T> G[100005];
int dist[100005];
bool check(int mid) {
fill(dist, dist+N+1, INF);
priority_queue<P, vector<P>, greater<P> > que;
dist[1] = 0;
que.push(P(0, 1));
while(!que.empty()) {
P p = que.top(); que.pop();
int v = p.second;
if(dist[v] < p.first) continue;
for(auto &[u, a, b] : G[v]) {
if(b < mid) continue;
if(dist[u] > dist[v] + a) {
dist[u] = dist[v] + a;
que.push(P(dist[u], u));
}
}
}
return dist[N] <= X;
}
int main() {
cin >> N >> M >> X;
for(int i = 0; i < M; ++i) {
int u, v, a, b;
cin >> u >> v >> a >> b;
G[u].push_back(T(v, a, b));
G[v].push_back(T(u, a, b));
}
long long l = 0, r = 1e18+1;
while(r - l > 1) {
int mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
if(l==0) cout << -1 << endl;
else cout << l << endl;
return 0;
}