这里的dijsktra的变种代码是我看着自己打的,终于把代码和做法思路联系上了,也就是理解了算法——看来手跟着画一遍真的有助于理解。
#define _CRT_SECURE_NO_WARNINGS #include<string.h> #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int MAXN=210; #define typec double const typec INF=0x3f3f3f3f*1.0;//防止后面溢出,这个不能太大 bool vis[MAXN]; typec cost[MAXN][MAXN]; typec lowcost[MAXN]; void Dijkstra(int n,int beg) //连通图的最小边——最短路变种 { for(int i=0;i<n;i++) { lowcost[i]=INF;vis[i]=false; } lowcost[beg]=0.0; for(int i=0;i<n;i++) { typec temp=INF; int k=-1; for(int j=0;j<n;j++) { if(!vis[j]&&lowcost[j]<temp) { temp=lowcost[j]; k=j; } } vis[k]=true; for(int l=0;l<n;l++) { if(!vis[l]) { lowcost[l]=min(max(lowcost[k],cost[k][l]),lowcost[l]);//原来改动在这列,具体可画图求证感知 } } } } int main() { int n,i,j,id=1; typec a[MAXN],b[MAXN]; while(scanf("%d",&n),n) { for(i=0;i<n;i++) cost[i][i]=0; for(i=0;i<n;i++) { scanf("%lf%lf",&a[i],&b[i]); for(j=0;j<i;j++) { cost[i][j]=cost[j][i]=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])); } } Dijkstra(n,0); printf("Scenario #%d Frog Distance = %.3lf ",id++,lowcost[1]); } return 0; }