题目：

连接：点击打开链接

题意：

n个点，是每个点相互连通（直接间接），求最短距离。

思路：

prim（）最小生成树。把点的距离存在map中。

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define MAXN 110 #define MAX 100000000 struct node{ double x,y; }p[MAXN]; double map[MAXN][MAXN]; double low[MAXN]; int vis[MAXN]; int n; void prim() { int pos; double minn; double result = 0; memset(vis,0,sizeof(vis)); pos = 1; vis[pos] = 1; for(int i=1; i<=n; i++) { if(i != pos) low[i] = map[pos][i]; } for(int i=1; i
      
        low[j]) { minn = low[j]; pos = j; } } result += minn; vis[pos] = 1; for(int j=1; j<=n; j++) { if(!vis[j] && map[pos][j] < low[j]) low[j] = map[pos][j]; } } printf("%.2lf\n",result); } int main() { //freopen("input.txt","r",stdin); while(scanf("%d",&n) != EOF) { for(int i=1; i<=n; i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) map[i][j] = sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y)); } prim(); } return 0; } 
      
     
    
   
  

战斗，永不停歇~~~~~~~~~~~~~~~~~~~~~