新疆建設(shè)云網(wǎng)站投訴電話網(wǎng)絡(luò)營(yíng)銷推廣軟件
最小傳遞延遲
題目
通訊網(wǎng)絡(luò)中有N
個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)
用1 ~ N
進(jìn)行標(biāo)識(shí)
網(wǎng)絡(luò)通過(guò)一個(gè)有向無(wú)環(huán)圖進(jìn)行表示
其中圖的邊的值,表示節(jié)點(diǎn)之間的消息傳遞延遲
現(xiàn)給定相連節(jié)點(diǎn)之間的延時(shí)列表times[i]={u,v,w}
其中u
表示源節(jié)點(diǎn),v
表示目的節(jié)點(diǎn),w
表示u
和v
之間的消息傳遞延時(shí)
請(qǐng)計(jì)算給定源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小傳遞延遲
如果目的節(jié)點(diǎn)不可達(dá)請(qǐng)返回-1
注意:N的取值范圍是1 ~ 100
延遲times
列表長(zhǎng)度不超過(guò)6000
且1 <= u,v <= N,0 <= w <= 100
輸入
輸入第一行為兩個(gè)正整數(shù),分別為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)N
以及延時(shí)列表長(zhǎng)度M
,用空格分隔
接下來(lái)的M
行為兩個(gè)節(jié)點(diǎn)間的延時(shí)列表[u,v,w]
輸入的最后一行為兩個(gè)正整數(shù)u
和v
分別表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)
輸出
輸出一個(gè)整數(shù)表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小延時(shí)
示例一
輸入
3 3
1 2 11
2 3 13
1