| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 31854 | Accepted: 10262 |
Description
Input
Output
Sample Input
2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
大意：
从A到B有多条路径，先取每条路径的最大值，然后再求出它们的最小值。
比如三条路径，1 3 4；2 5，1 2 1；最大值分别为4，5，2，最小值就是2
使用DIjkstra算法的思路，lowcost[]此时不再是最短路径，而是从起点到结点i的所有路径的最大边中的最小值，算法中维护s集合，从未更新的结点中取出最小节点，不断向外进行扩展。
扩展方法：if（max(lowcost[u],w[u][v])<lowcost[v]）
lowcost[v]=max(lowcost[u],w[u][v])<lowcost[v];
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 using namespace std; 6 #define Max 300+10 7 #define MMax 0x3f3f3f3f 8 struct point 9 { 10 int x,y; 11 }; 12 double w[Max][Max]; 13 double lowcost[Max]; 14 bool vis[Max]; 15 point p[Max]; 16 int n; 17 double dis(point a,point b) 18 { 19 return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 20 } 21 void Dijkstra(int s) 22 { 23 for(int i=0;i<n;i++){ 24 lowcost[i]=MMax; /*memset按照字节来赋值，但是int是四个字节*/ 25 vis[i]=0; 26 } 27 lowcost[0]=0; 28 while(1) 29 { 30 int u=-1,v; 31 int i,j; 32 double Min=MMax; 33 for(v=0;v<n;v++) 34 if(!vis[v]&&(u==-1||lowcost[v]<lowcost[u])) 35 { 36 u=v; 37 } 38 if(u==-1) break; 39 vis[u]=1; 40 for(v=0;v<n;v++) 41 if(!vis[v]&&max(lowcost[u],w[u][v])<lowcost[v]) 42 lowcost[v]=max(lowcost[u],w[u][v]); 43 } 44 return; 45 } 46 int main() 47 { 48 int i,j,k,count=0; 49 //freopen("in.txt","r",stdin); 50 while(cin>>n&&n) 51 { 52 memset(w,0,sizeof(0)); 53 for(i=0;i<n;i++) 54 scanf("%d%d",&p[i].x,&p[i].y); 55 for(i=0;i<n-1;i++) 56 for(j=i+1;j<n;j++) 57 w[i][j]=w[j][i]=dis(p[i],p[j]); 58 Dijkstra(0); 59 printf("Scenario #%d\nFrog Distance = %0.3lf\n\n",++count,lowcost[1]); 60 } 61 }
原文：http://www.cnblogs.com/a1225234/p/4993639.html