3121 問題 S: 信息學(xué)奧賽一本通T1348-城市公交網(wǎng)建設(shè)問題
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 168 解決: 0
題目描述
有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少？
輸入
n（城市數(shù)，1<≤n≤100）
e（邊數(shù)）
以下e行，每行3個(gè)數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價(jià)。
輸出
n-1行，每行為兩個(gè)城市的序號(hào)，表明這兩個(gè)城市間建一條高速公路。
樣例輸入
5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情