AB國是一個非常不一樣的國家，在這個國家裡面的人民，他們沒有壽命限制、受傷再嚴重只要時間夠久也能夠恢復、甚至當身體灰飛煙滅後，人民也能從某個固定點復活，彷彿線上遊戲般砍掉也能重練。但也如線上遊戲般，大部分的人民沒有自主意識，有如NPC般遵守規律的作息，只有少部分的人才能隨自我意志來行動。
因為人們長生不死，偶而還會伴隨著新同伴的加入（原因不明，推測是在固定復活點處隨機產生，只是產生出來的人大部分都是NPC），這群人無所事事便想搞破壞（因為根本不會死），於是AB國在創建初期是毫無秩序的，直到「天使」現身。
「天使」是依照旨意下來管理AB國的人民（也就是從重生點出生），能力強大，若是有不遵守規矩的人民，他都能以最快的速度找到並制伏，最高紀錄曾經一天引發數次 Legendary ，可謂極其兇惡。
於是原來具有自主意識的人們（又復活了）開始團結起來，名為「英雄戰線聯盟」，為了恢復昔日的自由，與天使互相對抗。
在一次的戰役中，「戰線聯盟」發現天使出現在一處基地的前方不遠處，而那個基地正巧在進行著重要的會議，主要的領導都在裡面商討戰略，無法現身抵抗天使，因此在基地外守衛的你，必須盡快想出辦法，拖延到最多的時間，並祈禱內部的會議能盡早結束。
於是在來到AB國之前的你，回憶起曾經修過的程式設計，開始假想基地周圍有 N 處空地，空地之間總共會有M個通道相連，當天使在空地時，因為周圍沒有障礙物，可以展開能力到達這個空地的任意地方，但如果要在空地間移動，必須經由空地之間的通道，在此補充一下，有些人可能認為的的文章有Bug，認為前面我提到了「天使的能力強大」，為何不直接飛進基地就好了呢？理由如下：天使雖然強大，但他的能力最為優秀的只有兩項，一是戰技出眾，二是gank極強（這導因於他有內建GPS，等等這項能力也會有些用處），因而能殺爆全場。
扯回重點，因為每個通道的環境都不太相同，因此天使在通過通道時，會需要消耗一些時間，或多或少，天使當然也知道這回事，趕緊啟動腦內GPS，企圖以最短時間攻入基地。
當然天使的能力在「戰線聯盟」並不是秘密，於是聰明的你，拿起了手上的武器（電腦），也去試著攻擊其中一個通道，讓天使在通過這個通道時，所需時間加倍（你手上只有一台電腦，因此只能攻擊一個通道），當通道通過的時間改變後，天使將會重新計算新的最短通過時間，你的目的就是要讓他後來通過的時間，與原來通過的時間相比，延長時間相差最長。
（後記：雖然大家都及時趕出來對抗天使，但依舊被殺到Legendary滿天飛……）
輸入有多筆測資。
每筆測資第一行有兩正整數 N（1 <= N <= 1000）、M（1 <= M <= 100000），如題幹所述。此時，空地的編號為 1 ~ N，天使的初始位置在 1，基地在 N 。接著M行，每行有三個正整數 a、b（1 <= a, b <= N）、w（1 <= w <= 100000），代表空地 a 和空地 b 之間有條通道，通過這條通道的時間為 w。
輸入保證任意1~n的路徑之權重和不超過2^31-1
依題幹所述，輸出新的通過時間與原來通過時間相差的最大值。
5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2
2
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||