結果

問題 No.3490 最高経路問題
コンテスト
ユーザー yamate11
提出日時 2026-04-03 21:47:54
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 2,554 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,459 ms
コンパイル使用メモリ 343,496 KB
実行使用メモリ 11,680 KB
最終ジャッジ日時 2026-04-03 21:48:24
合計ジャッジ時間 7,673 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long int;
using u64 = unsigned long long;
using pll = pair<ll, ll>;
// #include <atcoder/all>
// using namespace atcoder;
#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define REPrev(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(coll) (coll).begin(), (coll).end()
#define SIZE(v) ((ll)((v).size()))
#define REPOUT(i, a, b, exp, sep) REP(i, (a), (b)) cout << (exp) << (i + 1 == (b) ? "" : (sep)); cout << "\n"

// @@ !! LIM(binsearch)

// ---- inserted library file binsearch.cc

template <typename T>
requires integral<T>
T binsearch(auto check, T yes, T no) {
  while (abs(no - yes) > 1) {
    T mid = yes + (no - yes) / 2;  // avoiding unnecessary overflow
    if (check(mid)) yes = mid;
    else            no  = mid;
  }
  return yes;
}

template <typename T>
requires floating_point<T>
T binsearch(auto check, T yes, T no, T err, const bool abs_only = false) {
  T rep_in_t = ceil(log(abs(yes - no) / err) / log(2.0));
  constexpr int lim = INT_MAX - 10;
  int rep = rep_in_t > (T)lim ? lim : llround(rep_in_t) + 1;
  for (int r = 0; r < rep; r++) {
    T mid = (yes + no) / 2.0;
    if (not abs_only) {
      if (abs(yes - mid) < err * min(abs(mid), abs(yes))) return mid;
    }
    if (check(mid)) yes = mid;
    else            no  = mid;
  }
  return yes;
}

// ---- end binsearch.cc

// @@ !! LIM -- end mark --

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, M; cin >> N >> M;
  // @InpNbrList(N, M, nbr, dec=1, read=H) [W60DNwf4]
  struct nbr_t {
    int nd;
    ll H;
    nbr_t(int nd_ = int(), ll H_ = ll()) : nd(nd_), H(H_) {}
  };
  auto nbr = vector(N, vector(0, nbr_t()));
  for (int i = 0; i < M; i++) {
    int u, v; cin >> u >> v; u -= 1; v -= 1;
    ll H; cin >> H;
    nbr[u].emplace_back(v, H);
    nbr[v].emplace_back(u, H);
  }
  // @End [W60DNwf4]

  ll big = 1e18;
  auto check = [&](ll x) -> bool {
    vector dist(N, big);
    queue<ll> que;
    dist[0] = 0;
    que.push(0);
    while (not que.empty()) {
      auto nd = que.front(); que.pop();
      if (nd == N - 1) return true;
      for (auto [peer, h] : nbr[nd]) {
        if (x <= h) {
          if (dist[peer] == big) {
            dist[peer] = dist[nd] + 1;
            que.push(peer);
          }
        }
      }
    }
    return false;
  };

  ll x = binsearch<ll>(check, 0, (ll)1e9 + 10);
  if (x == 0) {
    cout << "NaN\n";
  }else {
    cout << x << endl;
  }

  return 0;
}
0