本题为最短路径规划中的特殊例子,要求遍历所有的点
Description
lmh刚来到山师学习,他知道以后自己要在这里生活很长时间,所以想要尽快弄清楚学校里面各种设施的位置,方便以后找路。但是他又不希望总是走回头路,希望能够走最少的路来将所有的要了解的位置都认一遍,请已经熟知学校路的你为他规划一个路径,让他可以尽快融入山师。(出发的起点与终点不固定)
Input
第一行有两个数n和m,n表示有n个需要去探索的地点,m表示有m条道路。接下来的m行,每行形如“a b c”用来表示一条道路,意思是地点a到地点b需要走的路长度为c。(1<=n<=100,1<=m<=300,1<=a,b<=n,1<=c<=10000)
Output
输出走遍学校共走了多长的路。
Sample Input
6 9 2 4 11 3 5 13 4 6 3 5 6 4 2 3 6 4 5 7 1 2 1 3 4 9 1 3 2
Sample Output
19
17田健 2019/2/14 21:34:54 #include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 310; bool used[maxn]; int n, m,mincost[maxn], cost[maxn][maxn]; int prime() { for(int i = 0; i <= n; i++) { mincost[i] = INF; used[i] = false; } mincost[1] = 0; int res = 0; while(true) { int v = -1; for(int u = 1; u <= n; u++) { if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u; } if(v == -1) break; used[v] = true; res += mincost[v]; for(int u = 1; u <= n; u++) { mincost[u] = min(mincost[u], cost[v][u]); } } return res; } int main() { while(scanf("%d%d", &n, &m) != EOF) { for(int i = 0 ; i <= n; i++) { for(int j = 0; j <= n; j++) { cost[i][j] = INF; } } for(int i = 0; i <m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); cost[a][b] = c; cost[b][a] = c; } int result = prime(); printf("%d\n", result); } return 0; }