本题为最短路径规划中的特殊例子，要求遍历所有的点
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;
}
转载于:https://www.cnblogs.com/RootVount/p/10380907.html
相关资源：JAVA上百实例源码以及开源项目
