POJ 2253 Frogger -- 最短路变形
2024-10-15 07:52:24
这题的坑点在POJ输出double不能用%.lf而要用%.f。。。真是神坑。
题意:给出一个无向图,求节点1到2之间的最大边的边权的最小值。
算法:Dijkstra
题目每次选择权值最小的边进行延伸访问,最坏情况下每条路径都要访问,复杂度O(n^2)
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 207 struct point
{
int x,y;
}p[N]; int n;
double res,mini;
double way[N][N],d[N];
int vis[N]; void Dijastra()
{
int i,j,k;
for(i=;i<=n;i++)
d[i] = Mod;
d[] = ;
memset(vis,,sizeof(vis));
for(i=;i<=n;i++)
{
mini = Mod;
for(j=;j<=n;j++)
{
if(!vis[j] && d[j] <= mini)
{
k = j;
mini = d[j];
}
}
vis[k] = ;
if(res < d[k] && d[k] != Mod)
res = d[k];
if(k == )
return;
for(j=;j<=n;j++)
{
if(!vis[j])
d[j] = min(d[j],way[k][j]);
}
}
} double dis(point ka,point kb)
{
return sqrt((ka.x-kb.x)*(ka.x-kb.x)+(ka.y-kb.y)*(ka.y-kb.y));
} int main()
{
int cs = ,i,j;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
for(i=;i<=n;i++)
{
for(j=i;j<=n;j++)
{
way[i][j] = way[j][i] = dis(p[i],p[j]);
}
way[i][i] = ;
}
res = ;
Dijastra();
printf("Scenario #%d\n",cs++);
printf("Frog Distance = %.3f\n\n",res); // %.3f
}
return ;
}
最新文章
- HTML5_01之表单新特性
- RabbitMQ 参数们的Power &ldquo;续&rdquo;
- 检测IP地址的正则表达式
- jquery控制滚动条改变上面固定(fixed)导航条或者搜索框的属性
- MySQL的InnoDB索引原理详解 (转)
- SharePoint 2013中的爬网最佳做法
- HW5.7
- python中xrange()和range()函数的区别使用:
- HEAP[xxx.exe]:Invalid Address specified to RtlValidateHeap 错误的解决方法总结
- 【LeetCode】【Python】Linked List Cycle
- CSS3 Pie工具可以让IE6至IE8版本实现大多数的CSS3修饰特性,如圆角、阴影、渐变等
- 设置 zend studio 默认编码为UTF8
- EDA 事件驱动框架
- 如何显示mnist中的数据(tensroflow)
- 如何利用keytool查看一个apk的签名
- Web 动画帧率(FPS)计算
- bzoj 4399 魔法少女LJJ
- SQLSERVER列出所有用户权限
- logstash快速入门实战指南-Logstash简介
- PAT L2-027 名人堂与代金券
热门文章
- poolboy的坑
- 【JWPlayer】官方JWPlayer去水印步骤
- margin和padding对行内元素的影响
- [ javascript New Image() ] New Image() 对象讲解
- SharePoint 2010 External List Paging &ndash; Server Side
- Oracle EBS在编码方式为AL32UTF8时的注意事项
- Echarts ecomfe 触摸屏 touch 在IE10下无法显示悬浮框
- NSOperation创建队列
- 安卓第十四天笔记-内容提供者(ContentProvider)
- jvm运行时环境属性一览