http://poj.org/problem?id=2502

同一条地铁线上的站点相邻点间按照v2建边,然后所有点之间按照v1更新建边,所有的边都是双向边,both directions。

然后直接跑dij就好了,防止因为重复的站点多建了同样的点,把上限开到了500,AC。

一个小bug是因为数组开了500,然后初始化时访问了500导致越界,,,把其他位置的地址更改了检查了半天,衰,以后还是多开几十好点。

 #include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
#define inf 999999999
double e[][];
struct node
{
int x,y;
}P[];
double dis(node A,node B)
{
double d1=(A.x-B.x)*(A.x-B.x),d2=(A.y-B.y)*(A.y-B.y);
return sqrt(d1+d2);
}
double dij(int N)
{
double d[];
bool vis[];
memset(vis,,sizeof(vis));
for(int i=;i<=N;++i) d[i]=inf;
d[]=;
for(int i=;i<=N;++i)
{
int u;
double minv=inf;
for(int j=;j<=N;++j) if(!vis[j]&&d[j]<minv) minv=d[u=j];
vis[u]=;
for(int j=;j<=N;++j)
if(!vis[j]&&d[j]>d[u]+e[u][j])
d[j]=d[u]+e[u][j];
}
return d[];
}
int main()
{
freopen("in.txt","r",stdin);
int N,M,i,j,k;
double v1=10000.0/;
double v2=40000.0/;
while(cin>>P[].x>>P[].y>>P[].x>>P[].y){
int p=,l=,a,b;
for(i=;i<;++i)
for(j=;j<;++j)
e[i][j]=(i==j?:inf);
while(cin>>a>>b){
if(a==-&&b==-) {l=p+;continue;}
++p;
P[p].x=a;
P[p].y=b;
if(p>l) e[p-][p]=e[p][p-]=min(e[p][p-],dis(P[p],P[p-])/v2);
} for(i=;i<=p;++i)
for(j=i+;j<=p;++j)
e[i][j]=e[j][i]=min(e[i][j],dis(P[i],P[j])/v1);
printf("%.0f\n",dij(p));
}
return ;
}

最新文章

  1. Eclipse+maven创建webapp项目&lt;二&gt;(转)
  2. 移动终于hold不住了 联合微信正式推出流量红包业务
  3. vs2012编译Qwt
  4. [ACM_水题] ZOJ 3706 [Break Standard Weight 砝码拆分,可称质量种类,暴力]
  5. cognos 10.2.2 导入samples数据源报错解决
  6. centos上如何安装git
  7. jquery滚动到指定元素,模仿锚点
  8. hyper-v新内容
  9. 移动应用开发(IOS/android等一下)在一般图像缓存方案评述(附流程图)
  10. MEF框架在Silverlight中应用(15)
  11. Sublime Text编辑器如何隐藏顶部的菜单栏
  12. [Cerc2013]Magical GCD
  13. python 字典实现简单购物车
  14. Git 分支模型
  15. DatePickerAndroid用法
  16. hdu-2222(ac自动机模板)
  17. leetcode 翻转二叉树
  18. (笔记)Linux下的解压、压缩命令集合
  19. jsonp 跨域1
  20. java 多线程知识点

热门文章

  1. .net ASPxGridView 使用手记
  2. Docker Libnetwork driver API
  3. ThreadLocal 示例
  4. getElementsByClassName - 兼容详细介绍
  5. day3-python-文件操作(2)
  6. String与反序
  7. Oracle事务和锁机制
  8. javascript Date对象 之 date初始化
  9. hadoop16---反射
  10. 介绍Web项目中用到的几款表单验证插件