a124: NOI2003 Day2.1.逃学的小孩
標籤 :
通過比率 : 100% (9 人 / 9 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2014-11-01 02:32

內容

Chris家的电话铃响起了,里面传出了 Chris的老师焦急的声音:“喂,是 Chris的家长吗?你们的孩子又没来上课,不想参加考试了吗?”一听说要考试, Chris的父母就心急如焚,他们决定在尽量短的时间内找到 Chris。他们告诉 Chris的老师:“根据以往的经验,Chris现在必然躲在朋友 Shermie或 Yashiro家里偷玩《拳皇》游戏。现在,我们就从家出发去找 Chris,一但找到,我们立刻给您打电话。 ”说完砰的一声把电话挂了。

Chris居住的城市由 N个居住点和若干条连接居住点的双向街道组成,经过街道 x需花费 Tx分钟。可以保证,任两个居住点间有且仅有一条通路。 Chris家在点 C,Shermie和 Yashiro分别住在点 A和点 B。Chris的老师和 Chris的父母都有城市地图,但 Chris的父母知道点 ABC的具体位置而 Chris的老师不知

为了尽快找到 Chris,Chris的父母会遵守以下两条规则:

1、如果A 距离C 比B 距离C 近,那么Chris 的父母先去Shermie 家寻找
Chris,如果找不到,Chris的父母再去Yashiro 家;反之亦然。

2、Chris 的父母总沿着两点间唯一的通路行走。 

显然,Chris的老师知道 Chris的父母在寻找 Chris的过程中会遵守以上两条规则,但由于他并不知道 A,B,C的具体位置,所以现在他希望你告诉他,最坏情况下 Chris的父母要耗费多长时间才能找到 Chris?

例如上图,这座城市由 4个居住点和 3条街道组成,经过每条街道均需花费 1分钟时间。假设 Chris住在点 C,Shermie住在点 A,Yashiro住在点 B,因为 C到 B的距离小于 C到 A的距离,所以 Chiris的父母会先去 Yashiro家寻找 Chris,一旦找不到,再去 Shermie家寻找。这样,最坏情况下 Chris的父母需要花费 4分钟的时间才能找到 Chris。

輸入說明

第一行是两个整数N(3 ≤ N ≤ 200000)和M,分别表示居住点总数和街道总数。以下M 行,每行给出一条街道的信息。第i+1 行包含整数Ui、Vi、Ti(1<= Ui, Vi <= N,1 ≤ Ti ≤ 1000000000),表示街道i 连接居住点Ui 和Vi,并且经过街道i 需花费Ti 分钟。街道信息不会重复给出。

輸出說明

输出仅包含整数T,即最坏情况下Chris 的父母需要花费T分钟才能找到Chris。

範例輸入
4 3
1 2 1
2 3 1
3 4 1
範例輸出
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (15%): 2.0s , <1K
公開 測資點#1 (15%): 2.0s , <1K
公開 測資點#2 (15%): 2.0s , <1M
公開 測資點#3 (15%): 2.0s , <1M
公開 測資點#4 (15%): 2.0s , <1M
公開 測資點#5 (25%): 2.0s , <10M
提示 :
標籤:
出處:
NOI2003Day2第一题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」