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