国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發(fā)設計 > 正文

1017_還是暢通工程

2019-11-14 09:49:20
字體:
供稿:網(wǎng)友
// 1017_還是暢通工程.cpp : 定義控制臺應用程序的入口點。//題目1017:還是暢通工程//時間限制:1 秒內(nèi)存限制:32 兆特殊判題:否提交:6085解決:3025//題目描述://某省調(diào)查鄉(xiāng)村交通狀況,得到的統(tǒng)計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通(但不一定有直接的公路相連,只要能間接通過公路可達即可),并要求鋪設的公路總長度為最小。請計算最小的公路總長度。//輸入://測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數(shù)目N ( < 100 );隨后的N(N-1)/2行對應村莊間的距離,每行給出一對正整數(shù),分別是兩個村莊的編號,以及此兩村莊間的距離。為簡單起見,村莊從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; //已經(jīng)加入集合的點的個數(shù) 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*/
發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 额济纳旗| 武安市| 镇江市| 手游| 新郑市| 安塞县| 基隆市| 宽城| 麻江县| 美姑县| 丽水市| 湾仔区| 广饶县| 盘山县| 大理市| 汽车| 共和县| 台山市| 图木舒克市| 武汉市| 榕江县| 聂拉木县| 历史| 呼图壁县| 庐江县| 丽水市| 河源市| 肃南| 托克托县| 济宁市| 道孚县| 吴桥县| 饶平县| 珠海市| 阿瓦提县| 合作市| 永城市| 榕江县| 两当县| 阿尔山市| 青铜峡市|