藍(lán)橋杯 C最短路問題
問題描述
給定一個(gè)n個(gè)頂點(diǎn)，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)環(huán)）。請你計(jì)算從1號點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號）。
輸入格式
第一行兩個(gè)整數(shù)n, m。
接下來的m行，每行有三個(gè)整數(shù)u, v, l，表示u到v有一條長度為l的邊。
輸出格式
共n-1行，第i行表示1號點(diǎn)到i+1號點(diǎn)的最短路。
樣例輸入
3 3
1 2 -1
2 3 -1
3 1 2
樣例輸出
-1
-2
數(shù)據(jù)規(guī)模與約定
對于10%的數(shù)據(jù)，n = 2，m = 2。
對于30%的數(shù)據(jù)，n <= 5，m <= 10。
對于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。
- 上一篇
藍(lán)橋杯 最小方差生成樹問題
問題描述給定帶權(quán)無向圖，求出一顆方差最小的生成樹。輸入格式輸入多組測試數(shù)據(jù)。第一行為N,M，依次是點(diǎn)數(shù)和邊數(shù)。接下來M行，每行三個(gè)整數(shù)U,V,W，代表連接U,V的邊，和權(quán)值W。保證圖連通。n=m=0標(biāo)志著測試文件的結(jié)束。輸出格式對于每組數(shù)據(jù)，輸出最小方差，四舍五入到0.01。輸
- 下一篇
藍(lán)橋杯 C最大最小公倍數(shù)
問題描述已知一個(gè)正整數(shù)N，問從1~N中任選出三個(gè)數(shù)，他們的最小公倍數(shù)最大可以為多少。輸入格式輸入一個(gè)正整數(shù)N。輸出格式輸出一個(gè)整數(shù)，表示你找到的最小公倍數(shù)。樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1 <= N <= 106。
相關(guān)資訊
