[kuangbin带你飞]专题四 最短路练习 POJ 2253 Frogger

求第一个点到第二个点的所有通路上最长的边

dijkstra的变形 每次松弛的是每条边通路上的的最长的边

WA了好几次是因为用了%lf 改成%f就过了……

 /* ***********************************************
Author :Sun Yuefeng
Created Time :2016/10/22 14:18:06
File Name :A.cpp
************************************************ */ #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<bitset>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<queue>
#include<list>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e2+;
const int mod=1e7+;
int dx[]= {,,,-,,-,,-};
int dy[]= {,-,,,-,,,-}; int n,m;
double way[maxn][maxn];
double dis[maxn];
bool vis[maxn]; struct point{
int x,y;
double dist(point a){
return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));
}
}pt[maxn]; void dijkstra(int x){
for(int i=;i<n;i++){
dis[i]=way[][i];
vis[i]=false;
}
dis[x]=;
for(int i=;i<n;i++){
int k=-;
double min=inf;
for(int j=;j<n;j++){
if(!vis[j]&&dis[j]<min){
min=dis[j];
k=j;
}
}
if(k==) break;
vis[k]=true;
for(int j=;j<n;j++){
if(!vis[j]&&dis[j]>max(dis[k],way[j][k])){
dis[j]=max(dis[k],way[j][k]);
}
}
}
printf("Frog Distance = %.3f\n\n",dis[]);
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int _case=;
while(~scanf("%d",&n)&&n){
printf("Scenario #%d\n",_case++);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
way[i][j]=inf;
for(int i=;i<n;i++)
scanf("%d%d",&pt[i].x,&pt[i].y);
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(i==j) continue;
way[i][j]=pt[i].dist(pt[j]);
way[j][i]=pt[i].dist(pt[j]);
}
}
dijkstra();
}
return ;
}
上一篇:Ruby开发入门


下一篇:mac怎么快速回到桌面 隐藏所有窗口