求第一个点到第二个点的所有通路上最长的边
dijkstra的变形 每次松弛的是每条边通路上的的最长的边
WA了好几次是因为用了%lf 改成%f就过了……
1 /* *********************************************** 2 Author :Sun Yuefeng 3 Created Time :2016/10/22 14:18:06 4 File Name :A.cpp 5 ************************************************ */ 6 7 #include<cstdio> 8 #include<iostream> 9 #include<algorithm> 10 #include<cmath> 11 #include<cstring> 12 #include<string> 13 #include<bitset> 14 #include<map> 15 #include<set> 16 #include<stack> 17 #include<vector> 18 #include<queue> 19 #include<list> 20 #define M(a,b) memset(a,b,sizeof(a)) 21 using namespace std; 22 typedef long long ll; 23 const int inf=0x3f3f3f3f; 24 const int maxn=2e2+10; 25 const int mod=1e7+7; 26 int dx[8]= {0,0,1,-1,1,-1,1,-1}; 27 int dy[8]= {1,-1,0,0,-1,1,1,-1}; 28 29 int n,m; 30 double way[maxn][maxn]; 31 double dis[maxn]; 32 bool vis[maxn]; 33 34 struct point{ 35 int x,y; 36 double dist(point a){ 37 return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y)); 38 } 39 }pt[maxn]; 40 41 void dijkstra(int x){ 42 for(int i=0;i<n;i++){ 43 dis[i]=way[0][i]; 44 vis[i]=false; 45 } 46 dis[x]=0; 47 for(int i=0;i<n;i++){ 48 int k=-1; 49 double min=inf; 50 for(int j=0;j<n;j++){ 51 if(!vis[j]&&dis[j]<min){ 52 min=dis[j]; 53 k=j; 54 } 55 } 56 if(k==1) break; 57 vis[k]=true; 58 for(int j=0;j<n;j++){ 59 if(!vis[j]&&dis[j]>max(dis[k],way[j][k])){ 60 dis[j]=max(dis[k],way[j][k]); 61 } 62 } 63 } 64 printf("Frog Distance = %.3f ",dis[1]); 65 } 66 67 int main() 68 { 69 //freopen("in.txt","r",stdin); 70 //freopen("out.txt","w",stdout); 71 int _case=1; 72 while(~scanf("%d",&n)&&n){ 73 printf("Scenario #%d ",_case++); 74 for(int i=0;i<n;i++) 75 for(int j=0;j<n;j++) 76 way[i][j]=inf; 77 for(int i=0;i<n;i++) 78 scanf("%d%d",&pt[i].x,&pt[i].y); 79 for(int i=0;i<n;i++){ 80 for(int j=0;j<n;j++){ 81 if(i==j) continue; 82 way[i][j]=pt[i].dist(pt[j]); 83 way[j][i]=pt[i].dist(pt[j]); 84 } 85 } 86 dijkstra(0); 87 } 88 return 0; 89 }