T1084 茅佳源的圖論
進(jìn)入題目(只有山東省北鎮(zhèn)中學(xué)團(tuán)隊成員可以查看)
提交該題????????????????????????記錄列表
Ps.題目由鐘皓曦提供，特以感謝
題目背景
????????????????????????????????????????????????凈 TM 扯淡。
?????????????????????????????????????????????????????????——Naegi Makoto && Hinata Hajime
題目描述
???????茅大爺是個圖論高手，他給zhx出了一道題。我們都知道求最短路是一件很簡單的事，但是茅大爺現(xiàn)在說你可以選擇刪掉圖中的某一條邊。你需要選擇一條刪掉的邊來使得最短路的長度盡可能大（但是你要保證從起點仍然能夠到達(dá)終點）。我們默認(rèn)起點為1號點終點為號點，并且假定這是一張無向圖。這題還是太難了，zhx又跑路了，所以茅大爺把這道題扔給了你。
輸入輸出格式
輸入格式：
???????第一行兩個整數(shù)N,M，代表無向圖中有N個點M條邊。
???????接下來M行，每行三個數(shù)s,e,d，代表有一條s在e和之間長度d的邊。
輸出格式：
???????一行一個整數(shù)，代表刪掉一條邊之后最短路可能的最大值。
輸入輸出樣例
輸入樣例＃1:
4 4
1 2 3
1 3 3
2 4 1
3 4 1輸出樣例＃2:
4
說明
【樣例解釋】
???????刪除任意一條邊即可。
【數(shù)據(jù)規(guī)模與約定】
???????對于40%的數(shù)據(jù)，1 ≤N≤ 50。
???????對于70%的數(shù)據(jù)，1 ≤N≤ 100,1 ≤M≤ 500。
???????對于100%的數(shù)據(jù)，1 ≤N≤ 200,1 ≤M≤ 50000，可能有重邊和自環(huán)，所有的邊權(quán)都是正數(shù)且不超過10000。
