1017_還是暢通工程
2019-11-14 09:11:30
供稿：網友
// 1017_還是暢通工程.cpp : 定義控制臺應用程序的入口點。//題目1017：還是暢通工程//時間限制：1 秒內存限制：32 兆特殊判題：否提交：6085解決：3025//題目描述：//某省調查鄉村交通狀況，得到的統計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。請計算最小的公路總長度。//輸入：//測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( < 100 )；隨后的N(N-1)/2行對應村莊間的距離，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。//當N為0時，輸入結束，該用例不被處理。//輸出：//對每個測試用例，在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年浙江大學計算機及軟件工程研究生機試真題#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; //每次加入集合的點（第一個點是1） int min_dist = 0; //累加的距離 int count = 1; //已經加入集合的點的個數 int cursor = start; //記錄當前距集合最小距離的位置 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*/
