最小傳遞延遲

題目

通訊網(wǎng)絡(luò)中有 N 個網(wǎng)絡(luò)節(jié)點(diǎn)

用 1 ~ N 進(jìn)行標(biāo)識

網(wǎng)絡(luò)通過一個有向無環(huán)圖進(jìn)行表示

其中圖的邊的值，表示節(jié)點(diǎn)之間的消息傳遞延遲

現(xiàn)給定相連節(jié)點(diǎn)之間的延時列表 times[i]={u,v,w}

其中 u 表示源節(jié)點(diǎn)，v 表示目的節(jié)點(diǎn)，w 表示 u 和 v 之間的消息傳遞延時

請計算給定源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小傳遞延遲

如果目的節(jié)點(diǎn)不可達(dá)請返回 -1

注意：N 的取值范圍是 1 ~ 100

延遲 times 列表長度不超過6000

且 1 <= u,v <= N,0 <= w <= 100

輸入

輸入第一行為兩個正整數(shù)，分別為網(wǎng)絡(luò)節(jié)點(diǎn)個數(shù) N 以及延時列表長度 M ，用空格分隔

接下來的 M 行為兩個節(jié)點(diǎn)間的延時列表 [u,v,w]

輸入的最后一行為兩個正整數(shù) u 和 v 分別表示源節(jié)點(diǎn)和目的節(jié)點(diǎn)

輸出

輸出一個整數(shù)表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小延時

示例一

輸入

3 3

1 2 11

2 3 13

1 3 50

1 3

1

2

3

4

5

輸出

24

1

說明

1~3 的延時是 50，1~2~3 的延時是 11+13=24

所以 1~3 的最小延時就是 24

————————————————

版權(quán)聲明：本文為CSDN博主「夢想橡皮擦」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/hihell/article/details/128985679

華為od 2023 | 什么是華為od，od 薪資待遇，od機(jī)試題清單

https://dream.blog.csdn.net/article/details/128980730

華為OD機(jī)試真題大全，用 Python 解華為機(jī)試題 | 機(jī)試寶典

https://dream.blog.csdn.net/article/details/129221789

【華為OD機(jī)試】全流程解析+經(jīng)驗(yàn)分享,題型分享,防作弊指南）

https://blog.csdn.net/hihell/article/details/129111620

華為od機(jī)試，獨(dú)家整理 已參加機(jī)試人員的實(shí)戰(zhàn)技巧

https://dream.blog.csdn.net/article/details/129270511