| 题目名称 | 2583. 南极科考旅行 |
|---|---|
| 输入输出 | BitonicTour.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 KZNS
于2017-01-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：19， 提交：38， 通过率：50% | ||||
 Faller |
100 | 0.000 s | 0.00 MiB | C++ |
 AntiLeaf |
100 | 0.011 s | 1.03 MiB | C++ |
 KZNS |
100 | 0.014 s | 0.99 MiB | C++ |
 MistyEye |
100 | 0.015 s | 1.74 MiB | C++ |
|
AntiLeaf |
100 | 0.016 s | 1.03 MiB | C++ |
|
Faller |
100 | 0.469 s | 97.09 MiB | C++ |
|
Faller |
100 | 0.475 s | 97.09 MiB | C++ |
 rewine |
100 | 0.540 s | 10.23 MiB | C++ |
 chad |
100 | 0.676 s | 101.40 MiB | C++ |
 苦读依旧 |
100 | 0.725 s | 32.52 MiB | C++ |
| 关于 南极科考旅行 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
回复 @苦读依旧 :
Orz ，Orz rewine
2017-03-01 16:44
4楼
| ||||
|
找到zkw爆了的原因了，原来是if(dis[to]==dis[rt]+e[i].dis)出现了精度问题，改成if(fabs(dis[rt]+e[i].dis-dis[to])<EPS)就过了，而spfa不存在这一问题。
 _Itachi
2017-01-09 16:32
3楼
| ||||
|
前排%%%
强行网络流走起（犯了一堆低级错误，比如把zkw写挂了还调不出来，最后改成了spfa才过得。。） _Itachi
2017-01-09 16:04
2楼
| ||||
|
回复 @若连自己也无相信，那指望谁能信 :
改了 KZNS
2017-01-09 15:36
1楼
| ||||
【题目描述】
小美要在南极进行科考，现在她要规划一下科考的路线。
地图上有 N 个地点，小美要从这 N 个地点中 x 坐标最小的地点 A，走到 x 坐标最大的地点 B，然后再走回地点 A。
请设计路线，使得小美可以考察所有的地点，并且在从 A 到 B 的路程中，考察的地点的 x 坐标总是上升的，在从 B 到 A 的过程中，考察的地点的 x 坐标总是下降的。
求小美所需要走的最短距离（欧几里得距离）。
【输入格式】
输入共 N+1 行。
第 1 行包含 1 个正整数 N，表示地图上共有 N 个地点。
第 1 +(1) 至 1 +(N) 行，每行包含 2 个正整数 x, y，表示其中 1 个地点的坐标。
【输出格式】
输出共 1 行。
第 1 行包含一个浮点数，表示小美需要走的最短距离，保留两位小数。
【样例输入】
4 1 1 2 3 4 1 3 2
【样例输出】
8.06
【数据范围及约定】
对于前 20% 测试数据
3 <= N <= 6
1 <= x <= 20, 1 <= y <= 20
对于后 80% 测试数据
3 <= N <= 300
1 <= x <= 10000, 1 <= y <= 10000
对于全部测试点，保证每个点坐标的 x 值互不相同
【来源】
Bitonic Tour