Subway POJ - 2502 最短路
2024-10-10 06:59:04
题意:给出地铁线 起点和 终点 坐地铁速度为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 ;
}
最新文章
- GDB调试汇编分析
- iOS时间问题
- 【原】iOS优秀开源项目总结
- 利用jQuery实现CheckBox全选/全不选/反选
- 创建一个ROS msg
- R语言randomForest包实现随机森林——iris数据集和kyphosis数据集
- hdu 4674 Trip Advisor(缩点+倍增lca)
- Jersey(1.19.1) - Client API, Ease of use and reusing JAX-RS artifacts
- MySQL原生HA方案 – Fabric体验之旅
- Linux Shell逻辑运算符和表达式详解
- zookeeper系列之异步通知模式-Watcher
- 论文笔记 Generative Face Completion
- Java NIO FileVisitor 高效删除文件
- nginx 常见正则匹配符号表示
- BZOJ3613 南园满地堆轻絮 二分/贪心
- ssh架构之hibernate(五)hql语句狂练
- MySQL数据库索引(中)
- ubuntu 命令配置ip 网关 dns
- Atitit.spring体系结构大总结
- 201621123005《Java程序设计》第三周作业学习总结