主唱太拼命了
給你一個無向圖 G,每條邊上都有權值 w 代表距離為 w 公里。其中每個點都有一個紅綠燈,剛開始都是綠燈,在 ai+bit,t=0,1,2,... 秒開始的時候會切換號誌。你現在有一台車每秒前進一公里(很快吧),你想知道從 s 開到 t 至少需要幾秒。
第一行會有四個正整數 n,m,s,t 代表 G 有 n 個點,m 條邊,起點終點分別為 s,t。
接下來有 n 行,第 i 行上會有兩個正整數 ai,bi 代表第 i 個點上紅綠燈的切換時間。
再接下來有 m 行,第 i 行上有三個正整數 ui,vi,wi 代表第 i 條邊連接 ui,vi,邊權是 wi。
輸出一個正整數代表最少需要的秒數。
IOICamp 2020 Day4 pB