給你一個無向圖 $G$,每條邊上都有權值 $w$ 代表距離為 $w$ 公里。其中每個點都有一個紅綠燈,剛開始都是綠燈,在 $a_i+b_it, t=0, 1, 2, ...$ 秒開始的時候會切換號誌。你現在有一台車每秒前進一公里(很快吧),你想知道從 $s$ 開到 $t$ 至少需要幾秒。
第一行會有四個正整數 $n, m, s, t$ 代表 $G$ 有 $n$ 個點,$m$ 條邊,起點終點分別為 $s, t$。
接下來有 $n$ 行,第 $i$ 行上會有兩個正整數 $a_i, b_i$ 代表第 $i$ 個點上紅綠燈的切換時間。
再接下來有 $m$ 行,第 $i$ 行上有三個正整數 $u_i, v_i, w_i$ 代表第 $i$ 條邊連接 $u_i, v_i$,邊權是 $w_i$。
輸出一個正整數代表最少需要的秒數。
7 7 1 7 9 8 5 7 1 8 5 7 10 7 6 2 10 7 1 4 4 1 5 4 1 6 5 2 3 9 2 6 6 2 7 4 5 7 6
10
5 5 2 4 9 8 5 7 1 8 5 7 10 7 1 2 6 1 4 9 2 3 2 2 5 5 4 5 10
15
5 6 2 4 9 8 5 7 1 8 5 7 10 7 1 2 2 1 3 5 1 4 10 2 3 2 2 5 2 4 5 5
7
IOICamp 2020 Day4 pB
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資 | 0 |
2 | 0~32 | 無額外限制 | 100 |