題目 1945:
藍(lán)橋杯算法提高VIP-Subway Timing
時間限制: 2s
內(nèi)存限制: 192MB 提交: 4 解決: 0
題目描述
和很多現(xiàn)代化的城市一樣，斯德哥爾摩有一個發(fā)達(dá)的公共交通系統(tǒng)。而斯德哥爾摩公共交通的核心就是地鐵。一份地鐵的拓?fù)涞貓D里有不同的地鐵線路，以及他們之間的連接方式，如下圖。在這個問題中，你可以假定地鐵的地圖一定是樹形的，盡管斯德哥爾摩的地鐵實(shí)際上并非確實(shí)如此，例如圖中藍(lán)色和綠色的線路形成了一個環(huán)。
地鐵的拓?fù)鋱D并不關(guān)心地鐵系統(tǒng)的幾何性質(zhì)，比如說不同地鐵站之間的距離（以及相應(yīng)的旅行時間）。雖然斯德哥爾摩的大部分學(xué)生都知道，“Tekniska Hogskolan” (皇家理工學(xué)院) 和 “Universitetet” (斯德哥爾摩大學(xué))相隔是非常遠(yuǎn)的，但是如上這幅圖中卻沒有體現(xiàn)出來。
為了豐富這張地圖，你要寫一個程序，計(jì)算出任意相鄰地鐵站之間所需的旅行時間。幸運(yùn)的是，那些旅行時間是已知的，所以不需要你親自去測量。但問題是，實(shí)際測量出來的時間是以秒為單位，而畫在地圖上的時間卻是以分鐘為單位，而且必須是整數(shù)，所以需要你給出一個時間的估計(jì)。
一種自然的估計(jì)時間的方法可能是簡單地將所有的旅行時間轉(zhuǎn)往離其最近的整數(shù)取整。但是這有可能導(dǎo)致巨大的累計(jì)誤差。在斯德哥爾摩的地圖上，這種估計(jì)方法會導(dǎo)致在某兩個地鐵站之間的旅行時間的估計(jì)與實(shí)際時間出現(xiàn)一個將近15分鐘的偏差。為了避免這個，你的程序需要選擇一些相鄰地鐵站之間的旅行時間向上取整，其余的向下取整，從而使得點(diǎn)對之間最大的累計(jì)誤差最小。
地鐵的拓?fù)鋱D并不關(guān)心地鐵系統(tǒng)的幾何性質(zhì)，比如說不同地鐵站之間的距離（以及相應(yīng)的旅行時間）。雖然斯德哥爾摩的大部分學(xué)生都知道，“Tekniska Hogskolan” (皇家理工學(xué)院) 和 “Universitetet” (斯德哥爾摩大學(xué))相隔是非常遠(yuǎn)的，但是如上這幅圖中卻沒有體現(xiàn)出來。
為了豐富這張地圖，你要寫一個程序，計(jì)算出任意相鄰地鐵站之間所需的旅行時間。幸運(yùn)的是，那些旅行時間是已知的，所以不需要你親自去測量。但問題是，實(shí)際測量出來的時間是以秒為單位，而畫在地圖上的時間卻是以分鐘為單位，而且必須是整數(shù)，所以需要你給出一個時間的估計(jì)。
一種自然的估計(jì)時間的方法可能是簡單地將所有的旅行時間轉(zhuǎn)往離其最近的整數(shù)取整。但是這有可能導(dǎo)致巨大的累計(jì)誤差。在斯德哥爾摩的地圖上，這種估計(jì)方法會導(dǎo)致在某兩個地鐵站之間的旅行時間的估計(jì)與實(shí)際時間出現(xiàn)一個將近15分鐘的偏差。為了避免這個，你的程序需要選擇一些相鄰地鐵站之間的旅行時間向上取整，其余的向下取整，從而使得點(diǎn)對之間最大的累計(jì)誤差最小。
輸入格式
輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)最開始是一個整數(shù)N(1≤N≤100)，為地鐵站的個數(shù)。這N個地鐵站用正整數(shù)1到N標(biāo)記。接下來N-1行包含了三個整數(shù)a,b,t(1≤a,b≤n,1≤t≤300)，表示地鐵站a和站b是相鄰的，而且在它們之間旅行的時間花費(fèi)是t秒。為了簡化問題，忽略地鐵在地鐵站停留的時間。
輸入以EOF結(jié)束。
輸入以EOF結(jié)束。
輸出格式
對于每組數(shù)據(jù)，輸出數(shù)據(jù)組號（從1開始標(biāo)號），然后輸出對相鄰地鐵站之間的旅行時間進(jìn)行舍入之后，兩兩地鐵站之間旅行時間誤差的最大值所能取到的最小值。具體參照樣例所給定的格式。
樣例輸入
2 1 2 110 4 1 2 40 2 3 40 3 4 40 4 1 2 90 1 3 90 1 4 90
樣例輸出
Case 1: 10 Case 2: 40 Case 3: 60
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情