poj2502 Subway
2024-09-30 20:39:50
思路:
需要注意的地方:一条地铁线路并不一定和样例描述的那样是直的;同一条线路上的两个站点步行可能更快。
实现:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; const int MAXN = , INF = 0x3f3f3f3f;
int sx, sy, ex, ey;
double dis[MAXN][MAXN]; struct node
{
int x, y;
};
node a[MAXN]; int square(int x)
{
return x * x;
} double cal(int i, int j)
{
return sqrt((double)square(a[i].x - a[j].x) + (double)square(a[i].y - a[j].y));
} int main()
{
int x, y;
cin >> sx >> sy >> ex >> ey;
a[].x = sx; a[].y = sy;
int tmp = , cnt = ;
for (int i = ; i < MAXN; i++)
{
for (int j = ; j < MAXN; j++)
{
dis[i][j] = INF;
}
}
for (int i = ; i < MAXN; i++) dis[i][i] = ;
while (cin >> x >> y)
{
if (x == - && y == -)
{
for (int i = tmp; i < cnt - ; i++)
dis[i][i + ] = dis[i + ][i] = cal(i, i + ) / 40.0;
tmp = cnt;
continue;
}
a[cnt++].x = x; a[cnt - ].y = y;
}
a[cnt].x = ex; a[cnt].y = ey;
for (int i = ; i <= cnt; i++)
{
for (int j = i + ; j <= cnt; j++)
{
dis[i][j] = dis[j][i] = min(dis[i][j], cal(i, j) / 10.0);
}
}
for (int k = ; k <= cnt; k++)
{
for (int i = ; i <= cnt; i++)
{
for (int j = ; j <= cnt; j++)
if (dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
} cout << int(dis[][cnt] / 1000.0 * 60.0 + 0.5) << endl;
return ;
}
最新文章
- Cannot run gnome extension in browser
- 优秀的JavaScript开发框架
- Java经典实例:在正则表达式中控制大小写
- c#之第二课
- Speed-BI数据分析案例:2016年7月汽车销量排行榜
- Delphi RICHEDIT中插入图象
- jquery中这句 .stop(false,true); 什么意思
- 复习HTML+CSS(5)
- BZOJ 4804
- 了解Linux操作系统发展阶段
- 算法手记(2)Dijkstra双栈算术表达式求值算法
- 【Python】统计个人新浪微博词频并给出相应的柱状图
- js字符串转日期兼容性
- exists 的使用
- VS2015 编译前/后拷贝文件到指定目录
- 清理.git文件
- @class指令的使用
- Slitaz 中文定制手册
- Python入门-散点图绘制
- EntityFramework定向加载实体