题意:给出地铁线  起点和 终点  坐地铁速度为v2  走路为v1 求起点到终点的最短距离  (答案需要四舍五入这里坑了好久)

拿给出的地铁站点 和起点终点建边即可  然后跑个迪杰斯特拉

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double v1=10000.0/;
const double v2=40000.0/;
int n;
const int maxn=+;
double dist[maxn];
double cost[maxn][maxn];
int vis[maxn];
const double INF=1e30; struct Node{
double x,y;
}node[maxn]; double dis(const Node&a,const Node&b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} void Dijkstra(){
for(int i=;i<=n;i++){
dist[i]=INF;
}
memset(vis,,sizeof(vis));
dist[]=;
for(int j=;j<n;j++){
int k=-;
double minnum=INF;
for(int i=;i<=n;i++){
if(!vis[i]&&dist[i]<minnum){
minnum=dist[i];
k=i;
}
}
if(k==-)break;
vis[k]=;
for(int i=;i<=n;i++){
if(!vis[i]&&dist[k]+cost[k][i]<dist[i]){
dist[i]=dist[k]+cost[k][i];
}
}
}
}
int main(){
while(scanf("%lf%lf%lf%lf",&node[].x,&node[].y,&node[].x,&node[].y)==){
n=;
int cnt1=;
for(int i=;i<maxn;i++)
for(int j=;j<maxn;j++)
if(i!=j)cost[i][j]=INF;
else cost [i][j]=;
int x,y;
bool ok=; while(scanf("%d%d",&x,&y)==){
if(x==-&&y==-){
ok=;
continue;
}
n++;
node[n].x=x;
node[n].y=y;
if(ok){
cost[n][n-]=cost[n-][n]=min(cost[n][n-],dis(node[n],node[n-])/v2);
}
ok=;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
cost[i][j]=cost[j][i]=min(cost[i][j],dis(node[i],node[j])/v1);
}
Dijkstra();
cout << int( dist[] + 0.5 );
}
return ;
}

最新文章

  1. GDB调试汇编分析
  2. iOS时间问题
  3. 【原】iOS优秀开源项目总结
  4. 利用jQuery实现CheckBox全选/全不选/反选
  5. 创建一个ROS msg
  6. R语言randomForest包实现随机森林——iris数据集和kyphosis数据集
  7. hdu 4674 Trip Advisor(缩点+倍增lca)
  8. Jersey(1.19.1) - Client API, Ease of use and reusing JAX-RS artifacts
  9. MySQL原生HA方案 – Fabric体验之旅
  10. Linux Shell逻辑运算符和表达式详解
  11. zookeeper系列之异步通知模式-Watcher
  12. 论文笔记 Generative Face Completion
  13. Java NIO FileVisitor 高效删除文件
  14. nginx 常见正则匹配符号表示
  15. BZOJ3613 南园满地堆轻絮 二分/贪心
  16. ssh架构之hibernate(五)hql语句狂练
  17. MySQL数据库索引(中)
  18. ubuntu 命令配置ip 网关 dns
  19. Atitit.spring体系结构大总结
  20. 201621123005《Java程序设计》第三周作业学习总结

热门文章

  1. 朱晔和你聊Spring系列S1E10:强大且复杂的Spring Security(含OAuth2三角色+三模式完整例子)
  2. 2018年计划小目标(9月)PMP
  3. Python_装饰器进阶_32
  4. Django的路由层
  5. mybatis的mapper注入失败
  6. stark组件的增删改
  7. 第一部分之简单字符串SDS(第二章)
  8. node学习: package.json
  9. python自动化常见问题汇总
  10. yolo buffer is too small for requested array