最小傳遞延遲

題目

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

用 1 ~ N 進行標識

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

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

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

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

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

如果目的節(jié)點不可達請返回 -1

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

延遲 times 列表長度不超過6000

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

輸入

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

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

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

輸出

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

示例一

輸入

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

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

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

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

解題參考

• 華為od 2023 | 什么是華為od，od 薪資待遇，od機試題清單

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

• 華為OD機試真題大全，用 Python 解華為機試題 | 機試寶典

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

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

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

• 華為od機試，獨家整理 已參加機試人員的實戰(zhàn)技巧

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