結果

問題 No.2387 Yokan Factory
ユーザー そすうぽよそすうぽよ
提出日時 2023-07-21 21:37:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 596 ms / 5,000 ms
コード長 2,100 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 218,416 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2023-10-21 21:31:50
合計ジャッジ時間 8,835 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 1 ms
4,348 KB
testcase_15 AC 296 ms
13,824 KB
testcase_16 AC 183 ms
13,296 KB
testcase_17 AC 403 ms
13,776 KB
testcase_18 AC 509 ms
12,240 KB
testcase_19 AC 397 ms
9,740 KB
testcase_20 AC 289 ms
8,420 KB
testcase_21 AC 587 ms
11,712 KB
testcase_22 AC 277 ms
8,420 KB
testcase_23 AC 436 ms
9,476 KB
testcase_24 AC 284 ms
8,948 KB
testcase_25 AC 266 ms
7,100 KB
testcase_26 AC 539 ms
10,920 KB
testcase_27 AC 596 ms
11,712 KB
testcase_28 AC 4 ms
4,348 KB
testcase_29 AC 5 ms
4,348 KB
testcase_30 AC 5 ms
4,348 KB
testcase_31 AC 3 ms
4,348 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 3 ms
4,348 KB
testcase_34 AC 6 ms
4,348 KB
testcase_35 AC 4 ms
4,348 KB
testcase_36 AC 3 ms
4,348 KB
testcase_37 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <variant>

#define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(x) begin(x), end(x)
#ifdef ENV_LOCAL
#define dump \
  if (1) cerr
#else
#define dump \
  if (0) cerr
#endif

using namespace std;
using namespace std::string_literals;

using i32 = int32_t;
using i64 = int64_t;
using f64 = double;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;

// using namespace harudake;
using Weight = i64;
Weight INF = 2e18;
struct Edge {
  int src, dest;
  Weight weight;
  bool operator<(const Edge &rhs) const { return weight > rhs.weight; }
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
  g[dest].push_back((Edge){dest, src, weight});
}

// Dijkstra (Verified: AOJ2005)
void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  using P = pair<Weight, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    rep(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 n, m, x;
  cin >> n >> m >> x;
  vector<tuple<i64, i64, i64, i64>> edges;
  rep(i, m) {
    i64 u, v, a, b;
    cin >> u >> v >> a >> b;
    --u;
    --v;
    edges.emplace_back(u, v, a, b);
  }
  i64 le = -1, gt = 1e9 + 1;
  while (gt - le > 1) {
    i64 mid = (gt + le) / 2;
    Graph g(n);
    for (auto &&[u, v, a, b] : edges) {
      if (b < mid) continue;
      add_edge(g, u, v, a);
    }
    Array dist(n);
    dijkstra(g, dist, 0);
    if (dist[n - 1] <= x) {
      le = mid;
    } else {
      gt = mid;
    }
  }
  cout << le << endl;
  return 0;
}
0