4.70
AC代码:
#include<iostream> #include<cstdio> #include<string.h> #define MAX 999999; using namespace std; double map[105][105],dist[105]; bool isvisited[105]; double prime(int n) { int i,j,pos; double min,sum; sum=0; memset(isvisited,false,sizeof(isvisited)); //初始化 for(i=1; i<=n; i++) { dist[i]=map[1][i]; } //从1开始 isvisited[1]=true; dist[1]=MAX; //找到权值最小点并记录下位置 for(i=1; i<n; i++) { min=MAX; for(j=1; j<=n; j++) { if(!isvisited[j] && dist[j]<min) { min=dist[j]; pos=j; } } sum+=min; //加上权值 isvisited[pos]=true; //更新权值 for(j=1; j<=n; j++) { if(!isvisited[j] && dist[j]>map[pos][j]) { dist[j]=map[pos][j]; } } } return sum; } int main() { int n,a,b; double c; while("%d",scanf("%d",&n)) { for(int i=0; i<(n*(n-1)/2); i++)//n*(n-1)/2代表的是路的条数 { cin >> a>> b>>c; map[a][b]=map[b][a]=c; } double ans=prime(n);//n 代表的是城市的个数 printf("%.2f\n",ans); } return 0; }
|