刚开始没有理解题意,以为是最短路径,后来才发现是prim,哎,无语。。。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int maxn=201; const double INF=2<<20; double x[maxn],y[maxn],edge[maxn][maxn]; int n; double getd(int k,int j) { double ex=(x[k]-x[j])*(x[k]-x[j]); double ey=(y[k]-y[j])*(y[k]-y[j]); return sqrt(ex+ey); } double prim() { int i,j; double low[maxn]; int path[maxn],vis[maxn]; path[1]=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) edge[i][j]=getd(i,j); } for(i=1;i<=n;i++) { low[i]=i==1?0:INF; vis[i]=0; } double min; int k; for(i=1;i<=n;i++) { min=INF; for(j=1;j<=n;j++) { if(min>low[j]&&!vis[j]) { min=low[j]; k=j; } } vis[k]=1; for(j=1;j<=n;j++) { if(low[j]>edge[k][j]&&!vis[j]) { low[j]=edge[k][j]; path[j]=k; } } } double max=-1; i=2; while(i) { if(max<edge[path[i]][i]) max=edge[path[i]][i]; i=path[i]; } return max; } int main() { int t=0; while(cin>>n&&n) { t++; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; double ou=prim(); printf("Scenario #%d\n",t); printf("Frog Distance = %.3lf\n",ou); printf("\n"); } return 0; }