a462. Beats of the Angel
Tags :
Accepted rate : 29人/35人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-06-02 14:42

Content

AB國是一個非常不一樣的國家,在這個國家裡面的人民,他們沒有壽命限制、受傷再嚴重只要時間夠久也能夠恢復、甚至當身體灰飛煙滅後,人民也能從某個固定點復活,彷彿線上遊戲般砍掉也能重練。但也如線上遊戲般,大部分的人民沒有自主意識,有如NPC般遵守規律的作息,只有少部分的人才能隨自我意志來行動。

因為人們長生不死,偶而還會伴隨著新同伴的加入(原因不明,推測是在固定復活點處隨機產生,只是產生出來的人大部分都是NPC),這群人無所事事便想搞破壞(因為根本不會死),於是AB國在創建初期是毫無秩序的,直到「天使」現身。

「天使」是依照旨意下來管理AB國的人民(也就是從重生點出生),能力強大,若是有不遵守規矩的人民,他都能以最快的速度找到並制伏,最高紀錄曾經一天引發數次 Legendary ,可謂極其兇惡。

於是原來具有自主意識的人們(又復活了)開始團結起來,名為「英雄戰線聯盟」,為了恢復昔日的自由,與天使互相對抗。

在一次的戰役中,「戰線聯盟」發現天使出現在一處基地的前方不遠處,而那個基地正巧在進行著重要的會議,主要的領導都在裡面商討戰略,無法現身抵抗天使,因此在基地外守衛的你,必須盡快想出辦法,拖延到最多的時間,並祈禱內部的會議能盡早結束。

於是在來到AB國之前的你,回憶起曾經修過的程式設計,開始假想基地周圍有 N 處空地,空地之間總共會有M個通道相連,當天使在空地時,因為周圍沒有障礙物,可以展開能力到達這個空地的任意地方,但如果要在空地間移動,必須經由空地之間的通道,在此補充一下,有些人可能認為的的文章有Bug,認為前面我提到了「天使的能力強大」,為何不直接飛進基地就好了呢?理由如下:天使雖然強大,但他的能力最為優秀的只有兩項,一是戰技出眾,二是gank極強(這導因於他有內建GPS,等等這項能力也會有些用處),因而能殺爆全場。

扯回重點,因為每個通道的環境都不太相同,因此天使在通過通道時,會需要消耗一些時間,或多或少,天使當然也知道這回事,趕緊啟動腦內GPS,企圖以最短時間攻入基地。

當然天使的能力在「戰線聯盟」並不是秘密,於是聰明的你,拿起了手上的武器(電腦),也去試著攻擊其中一個通道,讓天使在通過這個通道時,所需時間加倍(你手上只有一台電腦,因此只能攻擊一個通道),當通道通過的時間改變後,天使將會重新計算新的最短通過時間,你的目的就是要讓他後來通過的時間,與原來通過的時間相比,延長時間相差最長。

(後記:雖然大家都及時趕出來對抗天使,但依舊被殺到Legendary滿天飛……)

Input

 

輸入有多筆測資。

每筆測資第一行有兩正整數 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

 

Output

依題幹所述,輸出新的通過時間與原來通過時間相差的最大值。

Sample Input #1
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
Sample Output #1
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1K
公開 測資點#3 (1%): 1.0s , <1M
公開 測資點#4 (1%): 1.0s , <1M
公開 測資點#5 (3%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (7%): 1.0s , <1M
公開 測資點#8 (7%): 1.0s , <10M
公開 測資點#9 (8%): 1.0s , <10M
公開 測資點#10 (10%): 1.0s , <10M
公開 測資點#11 (10%): 1.0s , <10M
公開 測資點#12 (10%): 1.0s , <10M
公開 測資點#13 (15%): 1.0s , <10M
公開 測資點#14 (20%): 1.0s , <10M
Hint :
2012/6/2 測資加強
Tags:
出處:
板橋高中練習題 [管理者: m80126colin (許胖) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」