这题的坑点在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 ;
}

最新文章

  1. HTML5_01之表单新特性
  2. RabbitMQ 参数们的Power &ldquo;续&rdquo;
  3. 检测IP地址的正则表达式
  4. jquery控制滚动条改变上面固定(fixed)导航条或者搜索框的属性
  5. MySQL的InnoDB索引原理详解 (转)
  6. SharePoint 2013中的爬网最佳做法
  7. HW5.7
  8. python中xrange()和range()函数的区别使用:
  9. HEAP[xxx.exe]:Invalid Address specified to RtlValidateHeap 错误的解决方法总结
  10. 【LeetCode】【Python】Linked List Cycle
  11. CSS3 Pie工具可以让IE6至IE8版本实现大多数的CSS3修饰特性,如圆角、阴影、渐变等
  12. 设置 zend studio 默认编码为UTF8
  13. EDA 事件驱动框架
  14. 如何显示mnist中的数据(tensroflow)
  15. 如何利用keytool查看一个apk的签名
  16. Web 动画帧率(FPS)计算
  17. bzoj 4399 魔法少女LJJ
  18. SQLSERVER列出所有用户权限
  19. logstash快速入门实战指南-Logstash简介
  20. PAT L2-027 名人堂与代金券

热门文章

  1. poolboy的坑
  2. 【JWPlayer】官方JWPlayer去水印步骤
  3. margin和padding对行内元素的影响
  4. [ javascript New Image() ] New Image() 对象讲解
  5. SharePoint 2010 External List Paging &ndash; Server Side
  6. Oracle EBS在编码方式为AL32UTF8时的注意事项
  7. Echarts ecomfe 触摸屏 touch 在IE10下无法显示悬浮框
  8. NSOperation创建队列
  9. 安卓第十四天笔记-内容提供者(ContentProvider)
  10. jvm运行时环境属性一览