K - 畅通工程再续
题目链接
题目大意：计算连通的最短路线的花费，但是要满足两点之间距离不小于10和不大于1000，如果不能连通，就输出oh！，能就输出最少花费。
思路：最小生成树问题，不过不是直接套prim模板了，做些小修改，详情看代码。
代码
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX=105;
const int inf=999999999;
double cost[MAX][MAX],mincost[MAX];
int n;
bool used[MAX];
struct point{
double x,y;
}e[MAX];
double prim(){
double res=0;
mincost[0]=0;
int cnt=0;
while(true){
int v=-1;
for(int i=0;i<n;i++){
if(!used[i]&&(v==-1||mincost[i]<mincost[v])) v=i;
}
if(v==-1||(v!=0&&mincost[v]==inf)) break;//如果所有点都已经用过或者无法继续连通了，就退出。
cnt++;//计数器，cnt-1就是最小生成树的边数。
used[v]=true;
res+=mincost[v];
for(int i=0;i<n;i++)
mincost[i]=min(mincost[i],cost[v][i]);
}
if(cnt==n) return res;//如果cnt-1==n，就说明可以连通。(最小生成树边数=顶点数-1)
else return -1;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
fill(mincost,mincost+MAX,inf);
fill(used,used+MAX,false);
for(int i=0;i<n;i++){
scanf("%lf%lf",&e[i].x,&e[i].y);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cost[i][j]=sqrt((e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y));
if(cost[i][j]<10||cost[i][j]>1000) cost[i][j]=inf;//如果边权大于1000或小于10，则不存在该边，设为inf。
}
}
double res=prim();
if(res==-1) puts("oh!");
else{
res=res*100;
printf("%.1f\n",res);
}
}
return 0;
}