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
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|