这道题有助于理解迪杰斯特拉的本质，感觉该算法更像是一种遍历图的思想而不仅仅是用来求最短路
题意是，每一条路径都有一个跳的最大值，比如在某一条路径中，跳的距离依次是2 3 1 6 5 那么这个最大值就是6. 任务是找出所有路径的最大值中的最小值
用d[j]表示从起始点到该点所有路径最大值中的最小值。
#include<math.h> #include<stdio.h> #include<string.h> #define max(a,b) (a>=b?a:b) #define MAX 1000 int n, x, y; int T=1; int mark[MAX]; double d[MAX]; struct point{ int x, y; }; struct point po[MAX]; void getpo(){ int i; for(i=1;i<=n;i++){ scanf("%d %d",&x,&y); po[i].x=x; po[i].y=y; } } double getdis(struct point a,struct point b){ double dis=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); return dis; } void dijkstra(){ int k, i, j; double min; memset(mark,0,sizeof(mark)); for(i=1;i<=n;i++) d[i]=MAX; d[1]=0; for(i=1;i<=n;i++){ min=MAX; for(j=1;j<=n;j++){ if(!mark[j]&&min>d[j]){ min=d[j]; k=j; } } if(k==2) break; mark[k]=1; for(j=1;j<=n;j++){ if(!mark[j] && d[j]>max(getdis(po[k],po[j]),d[k])) d[j]=max(getdis(po[k],po[j]),d[k]); } } printf("Scenario #%d\nFrog Distance = %.3lf\n\n",T++,d[2]); } int main(){ while(scanf("%d",&n)&&n!=0){ getpo(); dijkstra(); } return 0; }
但是不知道为什么这道题用c过了用c++就wa...
