POJ 2502 Subway (Dijkstra 最短+建设规划)

时间:2022-05-15 23:09:43
Subway
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6689   Accepted: 2176

Description

You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want
to be late for class, you want to know how long it will take you to get to school.


You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch
between different subway lines if you wish. All subway lines go in both directions.

Input

Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each
stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate
pair -1,-1. In total there are at most 200 subway stops in the city.

Output

Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.

Sample Input

0 0 10000 1000
0 200 5000 200 7000 200 -1 -1
2000 600 5000 600 10000 600 -1 -1

Sample Output

21

Source

Waterloo local 2001.09.22



题目链接:

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





题目大意:第一行给出起点和终点坐标,然后每一行是一个地铁线,用坐标表示,以-1 -1表示该条线路输入完成。注意单位是米!

每条线路都是直线双向。地铁时速40km/h,人步行速度10km/h,地铁仅仅能在相邻两站间行使,不能直接从第i站到第i+2站。若该人一到地铁站就有地铁坐,问其从起点到终点的最少须要几分钟



题目分析:此题的输入建图比較麻烦。每条地铁线我们要单独处理。笛卡尔距离 / 地铁速(40km/h)作为边权,处理完每条线,再处理其它点之间的边权,笛卡儿距离 / 人速(10km/h),然后就是裸的最短路问题,用Dijkstra求解,注意3个问题。第1:单位的换算,第2:结果要求四舍五入,第3:无穷大设置为double型!

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 405;
int const INF = 100000000.0; struct Node
{
double u, v;
}nd[MAX]; double dis[MAX], e[MAX][MAX];
bool vis[MAX];
int cnt; double get_dis(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
} void Dijkstra(int v0)
{
for(int i = 0; i < cnt; i++)
dis[i] = e[v0][i];
dis[v0] = 0;
vis[v0] = true;
for(int i = 0; i < cnt - 1; i++)
{
double mi = INF;
int u = v0;
for(int j = 0; j < cnt; j++)
{
if(!vis[j] && mi > dis[j])
{
u = j;
mi = dis[j];
}
}
vis[u] = true;
for(int k = 0; k < cnt; k++)
if(!vis[k] && dis[k] > dis[u] + e[u][k])
dis[k] = dis[u] + e[u][k];
}
} int main()
{
memset(vis, false, sizeof(vis));
memset(e, 0, sizeof(e));
scanf("%lf %lf %lf %lf", &nd[0].u, &nd[0].v, &nd[1].u, &nd[1].v);
double u, v;
int tmp = 2;
cnt = 2;
while(scanf("%lf %lf", &u, &v) != EOF)
{
if(u == -1.0 && v == -1.0)
{
for(int i = tmp; i < cnt - 1; i++)
{
double get = get_dis(nd[i].u, nd[i].v, nd[i + 1].u, nd[i + 1].v) / 40000.0;
e[i][i + 1] = e[i + 1][i] = get;
}
tmp = cnt;
continue;
}
nd[cnt].u = u;
nd[cnt++].v = v;
}
for(int i = 0; i < cnt; i++)
for(int j = i + 1; j < cnt; j++)
if(e[i][j] == 0)
e[i][j] = e[j][i] = get_dis(nd[i].u, nd[i].v, nd[j].u, nd[j].v) / 10000.0;
Dijkstra(0);
printf("%d\n", (int)(dis[1] * 60.0 + 0.5));
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

POJ 2502 Subway (Dijkstra 最短+建设规划)的更多相关文章

  1. POJ 2502 - Subway Dijkstra堆优化试水

    做这道题的动机就是想练习一下堆的应用,顺便补一下好久没看的图论算法. Dijkstra算法概述 //从0出发的单源最短路 dis[][] = {INF} ReadMap(dis); for i = 0 ...

  2. POJ 2502 Subway &sol; NBUT 1440 Subway &sol; SCU 2186 Subway(图论,最短距离)

    POJ 2502 Subway / NBUT 1440 Subway / SCU 2186 Subway(图论,最短距离) Description You have just moved from a ...

  3. Dijkstra&plus;计算几何 POJ 2502 Subway

    题目传送门 题意:列车上行驶40, 其余走路速度10.问从家到学校的最短时间 分析:关键是建图:相邻站点的速度是40,否则都可以走路10的速度.读入数据也很变态. #include <cstdi ...

  4. &lpar;简单&rpar; POJ 2502 Subway,Dijkstra。

    Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of ...

  5. poj 2502 Subway【Dijkstra】

    <题目链接> 题目大意: 某学生从家到学校之间有N(<200)条地铁,这个学生可以在任意站点上下车,无论何时都能赶上地铁,可以从一条地铁的任意一站到另一条地跌的任意一站,学生步行速度 ...

  6. POJ 2502 Subway(迪杰斯特拉)

    Subway Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6692   Accepted: 2177 Descriptio ...

  7. POJ 2502 Subway

    Subway Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4928   Accepted: 1602 Descriptio ...

  8. POJ 2502 Subway (最短路)

    Subway 题目链接: http://acm.hust.edu.cn/vjudge/contest/122685#problem/L Description You have just moved ...

  9. POJ 2502 Subway &lpar; 最短路 &amp&semi;&amp&semi; 最短路建图 &rpar;

    题意 : 给出二维平面上的两个点代表起点以及终点,接下来给出若干条地铁线路,除了在地铁线路上行进的速度为 40km/h 其余的点到点间都只能用过步行且其速度为 10km/h ,现问你从起点到终点的最短 ...

随机推荐

  1. html5 请求的URL转成 OC可用属性字符串显示

    NSData *data = [NSData dataWithContentsOfURL:[NSURL URLWithString:helpUrlStr]]; NSString *string = [ ...

  2. 【Python学习笔记】with语句与上下文管理器

    with语句 上下文管理器 contextlib模块 参考引用 with语句 with语句时在Python2.6中出现的新语句.在Python2.6以前,要正确的处理涉及到异常的资源管理时,需要使用t ...

  3. Execl DataTime Format Number

    Excel 中日期类型所保存的值是数值型.只是设置了为日期格式,通过公式转换从而得出我们平时常用的日期内容.也很好理解这公式所要说明的意思.数值是个浮点型可以分成2部分看.整数部分:年月日(日期)小数 ...

  4. sql server数据库中 INFORMATION&lowbar;SCHEMA的用法

    1.查询数据库的所有表: select * from INFORMATION_SCHEMA.TABLES 2.查询表名为xxx的所有列的信息 select * from INFORMATION_SCH ...

  5. Good Luck in CET-4 Everybody&excl;

    Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja ...

  6. python-ironicclient使用

    使用cli from ironicclient import client kwargs = {'os_username': 'ironic', 'os_password': 'IRONIC_PASS ...

  7. CentOS 6&period;x 如何升级 glibc 2&period;17

    CentOS 6.x 如何升级 glibc 2.17 ldd --version rpm -qa | grep glibc #查看glibc的版本 strings /lib64/libc.so.6 | ...

  8. 整理备忘一波liunx命令(持续更新)

    # 分区挂载 查看当前目录下的文件大小 du --max-depth= -h # 文件操作 # 编辑操作 #liunx 字体设置 苹果方字体下载安装 # 网洛端口 netstat命令各个参数说明如下: ...

  9. iPhone电源键坏了怎么开机和关机?

    一.开机 1.将USB数据线插到iPhone上,此时先不要将另一头插到电脑上 2.长按Home键不要动 3.将数据线的另一头插到电脑上 这时iPhone就会自动开机 二.关机 1.进入设置找到“通用” ...

  10. Actor模型---SwiftActors

    actor是一个无线程区别的内存访问对象:actor背后有线程支持:actor的事件处理依赖与这个线程(队列.池). actor是一种面向对象的线程(池)模型,强调对事件的响应:在iOS中相当于一种通 ...