poj 2253 Frogger (最短路变种,连通图的最长边)

题目

这里的dijsktra的变种代码是我看着自己打的,终于把代码和做法思路联系上了,也就是理解了算法——看来手跟着画一遍真的有助于理解。

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN=; #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=;i<n;i++)
{
lowcost[i]=INF;vis[i]=false;
}
lowcost[beg]=0.0;
for(int i=;i<n;i++)
{
typec temp=INF;
int k=-;
for(int j=;j<n;j++)
{
if(!vis[j]&&lowcost[j]<temp)
{
temp=lowcost[j];
k=j;
}
}
vis[k]=true;
for(int l=;l<n;l++)
{
if(!vis[l])
{
lowcost[l]=min(max(lowcost[k],cost[k][l]),lowcost[l]);//原来改动在这列,具体可画图求证感知
}
}
}
} int main()
{
int n,i,j,id=;
typec a[MAXN],b[MAXN];
while(scanf("%d",&n),n)
{
for(i=;i<n;i++)
cost[i][i]=; for(i=;i<n;i++)
{
scanf("%lf%lf",&a[i],&b[i]);
for(j=;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,);
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",id++,lowcost[]);
}
return ;
}
上一篇:JS正则汇总


下一篇:安装与配置2020Android studio