問題一覧 > 通常問題

No.3013 Headband-Buying Alien

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 187
作問者 : Apollo@Kuro / テスター : ゆにたりー卿 👑 loop0919 eom2357 DeltaStruct Yama.can Rice_tawara459 のらら あじゃじゃ 👑 binap
お気に入りにしたユーザー ProblemId : 11625 / 自分の提出
問題文最終更新日: 2025-01-25 11:24:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第1回 岩井星人アンソロジープログラミングコンテスト (順位表) の他の問題:

Problem Statement

To buy more headbands, Iwai Seijin has returned, carrying $Y$ yen, to his home Osaka Prefecture Planet Iwai.

Planet Iwai has $N$ towns, numbered $1, 2, \ldots, N$. Iwai Seijin is currently in Town $1$ , where the airport is located.

Planet Iwai also has $M$ roads connecting towns.
The $i$-th road connects Town $A_i$ and Town $B_i$ bidirectionally, and while traveling along it, he is shaken down for $C_i$ yen by bad people.
If he is shaken down while holding $X$ yen, the amount of money he holds becomes $\max(X - C_i, 0)$ yen.

Planet Iwai also has $P$ shops. The $i$-th shop is located in Town $D_i$ and sells headbands at $E_i$ yen per $1$ headband.
At a shop, he can buy any number of headbands, $0$ or more, as far as his money allows.
However, each $1$ town has at most $1$ shop.

Starting from Town $1$, how many headbands can Iwai Seijin buy?

Constraints

  • $2 \leq N \leq 2 × 10^5$
  • $1 \leq M \leq \min \left(2 × 10^5, \dfrac{N(N-1)}{2} \right)$
  • $1 \leq A_i < B_i \leq N\ (1 \leq i \leq M)$
  • $(A_i, B_i) \neq (A_j, B_j)\ (1 \leq i < j \leq M)$
  • $1 \leq C_i \leq 10^9\ (1 \leq i \leq M)$
  • $1 \leq P \leq N$
  • $1 \leq D_i \leq N\ (1 \leq i \leq P)$
  • $D_i \neq D_j\ (1 \leq i < j \leq P)$
  • $1 \leq E_i \leq 10^9\ (1 \leq i \leq P)$
  • $1 \leq Y \leq 10^{18}$
  • All input values are integers.

    • Input

    The input is given from standard input in the following format.

    $N\ M \ P\ Y$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_M\ B_M\ C_M$
$D_1\ E_1$
$D_2\ E_2$
$\vdots$
$D_P\ E_P$

    Output

    Print the maximum number of headbands Iwai Seijin can buy.

    Sample

    Sample 1
    Input
    3 3 2 19
1 3 4
2 3 1
1 2 5
2 5
3 4
    Output
    3

    Initially, Iwai Seijin has $19$ yen. After being shaken down for $5$ yen while moving from Town $1$ to Town $2$, he buys $1$ headband in Town $2$.
    From there, he moves to Town $3$, being shaken down for $1$ yen on the way, and buys $2$ headbands, for a total of $3$ headbands, so print 3.

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