1017_還是暢通工程

2019-11-14 09:49:20

字體：大中小

供稿：網(wǎng)友

// 1017_還是暢通工程.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。//題目1017：還是暢通工程//時(shí)間限制：1 秒內(nèi)存限制：32 兆特殊判題：否提交：6085解決：3025//題目描述：//某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計(jì)表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達(dá)即可），并要求鋪設(shè)的公路總長度為最小。請計(jì)算最小的公路總長度。//輸入：//測試輸入包含若干測試用例。每個(gè)測試用例的第1行給出村莊數(shù)目N ( < 100 )；隨后的N(N-1)/2行對應(yīng)村莊間的距離，每行給出一對正整數(shù)，分別是兩個(gè)村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。//當(dāng)N為0時(shí)，輸入結(jié)束，該用例不被處理。//輸出：//對每個(gè)測試用例，在1行里輸出最小的公路總長度。//樣例輸入：//3//1 2 1//1 3 2//2 3 4//4//1 2 1//1 3 4//1 4 1//2 3 3//2 4 2//3 4 5//0//樣例輸出：//3//5//來源：//2006年浙江大學(xué)計(jì)算機(jī)及軟件工程研究生機(jī)試真題#include "stdafx.h"#include "stdio.h"#include "iostream"#include "limits.h"#include "string.h"using namespace std;#define MAX 110int N;int dist[MAX][MAX],lowcost[MAX],visit[MAX];int main(){ while(cin>>N && N){ int x,y,z; for(int i = 0;i<N*(N-1)/2;i++){ cin>>x>>y>>z; dist[x][y] = dist[y][x] = z; } memset(visit,0,sizeof(visit)); for(int i = 2;i<=N;i++) lowcost[i] = INT_MAX; int start = 1; //每次加入集合的點(diǎn)（第一個(gè)點(diǎn)是1） int min_dist = 0; //累加的距離 int count = 1; //已經(jīng)加入集合的點(diǎn)的個(gè)數(shù) int cursor = start; //記錄當(dāng)前距集合最小距離的位置 visit[start] = 1; while(count<N){ for(int i =1;i<=N;i++){ if(!visit[i]){ lowcost[i] = min(lowcost[i],dist[start][i]); cursor = lowcost[i]<lowcost[cursor]?i:cursor; } } start = cursor; visit[start] = 1; count++; min_dist += lowcost[start]; lowcost[cursor] = INT_MAX; } cout<<min_dist<<endl; } return 0;}/*1.INT_MAX*/

上一篇：C語言逗號運(yùn)算符

下一篇：UML圖之實(shí)踐用例圖