問題一覧 > 通常問題

No.3013 ハチマキ買い星人

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 176
作問者 : Apollo@Kuro / テスター : 高橋ゆに 👑 loop0919 eom2357 DeltaStruct Yama.can こめだわら のらら あじゃじゃ 👑 binap
5 ProblemId : 11625 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-25 11:24:34

問題文

岩井星人さんはハチマキを買い足しに、YY 円を持った状態で故郷の大阪府岩井星に戻りました。

岩井星には NN 個の街があり、それぞれ 1,2,…,N1, 2, \ldots, N の番号が付いています。現在、岩井星人さんは空港のある街 11 に居ます。

また、岩井星には街と街をつなぐ MM 本の道路が存在します。
ii 番目の道路は街 AiA_i と街 BiB_i を双方向につないでおり、移動している最中に悪い人から CiC_i 円カツアゲされてしまいます。
所持金が XX 円の状態でカツアゲされると、所持金が max⁡(X−Ci,0)\max(X - C_i, 0) 円になります。

また、岩井星には PP 軒の店があり、ii 番目の店は街 DiD_i に存在し、11 本あたり EiE_i 円でハチマキを売っています。
店では、所持金の限り好きなだけ 00 本以上のハチマキを買うことができます。
ただし、11 つの街に存在する店は 11 軒以下です。

このとき、岩井星人さんは街 11 から出発し、どれだけ多くのハチマキを買うことができるでしょうか？

制約

  • 2≤N≤2×1052 \leq N \leq 2 × 10^5
  • 1≤M≤min⁡(2×105,N(N−1)2)1 \leq M \leq \min \left(2 × 10^5, \dfrac{N(N-1)}{2} \right)
  • 1≤Ai<Bi≤N (1≤i≤M)1 \leq A_i < B_i \leq N\ (1 \leq i \leq M)
  • (Ai,Bi)≠(Aj,Bj) (1≤i<j≤M)(A_i, B_i) \neq (A_j, B_j)\ (1 \leq i < j \leq M)
  • 1≤Ci≤109 (1≤i≤M)1 \leq C_i \leq 10^9\ (1 \leq i \leq M)
  • 1≤P≤N1 \leq P \leq N
  • 1≤Di≤N (1≤i≤P)1 \leq D_i \leq N\ (1 \leq i \leq P)
  • Di≠Dj (1≤i<j≤P)D_i \neq D_j\ (1 \leq i < j \leq P)
  • 1≤Ei≤109 (1≤i≤P)1 \leq E_i \leq 10^9\ (1 \leq i \leq P)
  • 1≤Y≤10181 \leq Y \leq 10^{18}
  • 入力される値は全て整数

    • 入力

    入力は以下の形式で標準入力から与えられる。

    N M P YN\ M \ P\ Y
A1 B1 C1A_1\ B_1\ C_1
A2 B2 C2A_2\ B_2\ C_2
⋮\vdots
AM BM CMA_M\ B_M\ C_M
D1 E1D_1\ E_1
D2 E2D_2\ E_2
⋮\vdots
DP EPD_P\ E_P

    出力

    岩井星人さんが買えるハチマキの最大数を出力せよ。

    サンプル

    サンプル1
    入力
    3 3 2 19
1 3 4
2 3 1
1 2 5
2 5
3 4
    出力
    3

    はじめ、岩井星人さんは 1919 円を持っています。 街 11 から街 22 へ移動するときに 55 円カツアゲされた後、街 22 でハチマキを 11 本買います。
    そこから 11 円カツアゲされながら街 33 に移動してハチマキを22本買うことで、合計 33 本買うことができるため3と出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。