他回家的路上要搭捷運
發布時間: July 14, 2018, 12:28 a.m. 最後更新時間: Sept. 27, 2023, 12:48 p.m. 時間限制: 2000ms 記憶體限制: 256M
你以為結束了嗎? 太天真了。
旲刓，一個充滿了魔法的國度，人人都擁有強大的魔術迴路，尤其是某些電神，隨手寫下的code(簡稱-咒碼)都擁有供應北旲刓三個月電量的電神力，電爆一大群人。
身為在魔法路上打滾的少年Sia喵，每次在旲大的齜牙上完培訓課後，都要回家(?)。
然而，回家的路必然是充滿阻撓的，除了每周三百魔力的傳送陣票卷，還有在傳送陣上的作業(殺怪)時間，他回家的路上要搭捷運!
重點是，Sia是個吃貨(?!)，喜歡到處吃東西，尤其是跟同學在科技小樓附近吃晚餐。
但今天同學都各自回家了...
Sia喵難過的看了看手錶，發現自己有大~量的時間可以享受大~量的食物，嗯，我是說，真的很大量。
所以...當他在科技小樓站上車前查看時間時，顯示的數字已經是神奇的10：23了。
然而...不知道到底是在晚餐時間吃了什麼的Sia醬不知道為什麼在車上一路都是昏昏沉沉，不知道為什麼大家都不覺得是因為被電神電了一天的原因？
總之Sia在小安海洋公園站看見的時間是10：28，但是在三站後的竹河北京站所看見的時間竟然是驚為天人的09：42。
這是怎麼回事？！原來亣旲北地區的大眾快捷交通路網居然設定有此等神奇的咒碼！
「我回到過去了啊啊啊啊啊!!!」
Sia急忙蒐集了兩站間要花的時間，作為電爆他的電神朋友，快來幫幫Sia醬吧?
已經有點頭殼壞去的Sia突發奇想想要測試行地宮到中海國小之間的時間究竟是多久？甚至可能是負的呢？！...不，怎麼可能，絕對只是Sia醬喝多了而已....
範例測資依然是捷運地圖呢喵www
第一行有三個數字N、E、Q,分別代表捷運站數、有多少條捷運線讓兩站相連、跟Sia要問的問題數。
接下來有E行，每行有a、b、v三個正整數，代表捷運線的資料，其中捷運會從站a出發，到站b，其中會花費v的時間(v可能為負數)，注意，就這條捷運線而言，b並不能到a，也就是這是一條單向的捷運線。
再來還有Q行，每行有s、e兩個點，分別代表Sia想要詢問的路徑的起點跟終點。
在20%的測資中 1<N<=20,1<=E<380,Q=50
在60%的測資中 1<N<=1000,1<=E<999000,Q=100
在100%的測資中 1<N<10000,1<=E<N(N-1),1<=s<e<=N,1<=a、b<=N,-10000<=v<=10000,Q=100
(此百分比數為向上包含)
請輸出Sia想詢問的路徑最少需花多少時間到達，若無法到達，請輸出"No"(不含引號)
20 44 1 1 2 5 2 3 5 3 4 5 4 5 5 5 6 5 6 7 5 7 6 5 6 5 5 5 4 5 4 3 5 3 2 5 2 1 5 2 14 5 14 12 5 12 11 5 11 8 5 8 7 5 7 17 5 17 18 5 18 17 5 17 7 5 7 8 5 8 11 5 11 12 5 12 14 5 14 2 5 15 5 5 5 12 5 12 13 5 13 10 5 10 9 5 9 8 5 8 9 5 9 10 5 10 13 5 13 12 5 12 5 5 5 15 5 15 16 5 16 18 5 18 20 5 20 18 5 18 16 5 16 15 5 1 20
40
