| 题目名称 | 1241. [NOIP 2010冲刺十三]逃离遗迹 |
|---|---|
| 输入输出 | escapeb.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sywgz
于2012-10-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：121， 提交：184， 通过率：65.76% | ||||
 LCWhiStLe |
100 | 0.000 s | 0.00 MiB | C++ |
 沉迷学习的假的Keller |
100 | 0.023 s | 0.62 MiB | C++ |
 粘粘自喜 |
100 | 0.025 s | 0.76 MiB | C++ |
 Magic_Sheep |
100 | 0.028 s | 0.76 MiB | C++ |
 Lethur |
100 | 0.031 s | 0.62 MiB | C++ |
 stdafx.h |
100 | 0.031 s | 1.87 MiB | C++ |
|
stdafx.h |
100 | 0.034 s | 2.88 MiB | C++ |
|
stdafx.h |
100 | 0.034 s | 3.20 MiB | C++ |
|
stdafx.h |
100 | 0.035 s | 1.87 MiB | C++ |
 <蒟蒻>我要喝豆奶 |
100 | 0.035 s | 2.28 MiB | C++ |
| 本题关联比赛 | |||
| 20121030 | |||
| 关于 逃离遗迹 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我偏要lca！！！
楼上强行spfa啊。。您家spfa都要退化成bfs了啊 | ||||
|
边表又开小了。。。
 liu_runda
2016-06-01 10:02
16楼
| ||||
|
三遍spfa秒之。
| ||||
 殇
2015-06-13 12:02
14楼
| ||||
|
回复 @溪哥 :
咬我啊~\(≧▽≦)/~啦啦啦 <蒟蒻>我要喝豆奶
2015-06-13 09:20
13楼
| ||||
|
回复 @我要喝豆奶 :
秦天繓，我鄙视你，粘我程序还比我快 | ||||
|
回复 @溪哥 :
貌似评测机更新了 <蒟蒻>我要喝豆奶
2015-06-13 07:01
11楼
| ||||
|
“优化是无止境的！”——亚梦溪曾经说过
| ||||
|
考试时候一遍秒过，都不知道怎么这么顺！
 | ||||
|
殇
2015-06-12 20:22
8楼
| ||||
Rapiz
\
神利·代目
lenibomb【题目描述】
根据外星人的回信，在遗迹分布着三样道具。当三样道具都拿走后，遗迹就很快自动毁灭，所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-l条长度不等通道所组成，并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A，B，C的房间内拿到道具，并且准备撤退。由于只有一架直升机，所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上，能够使三人到达该房间的距离之和最短。
【输入格式】
第1行：四个整数N、A、B、C。
第2..N行：每行三个整数u，v，w，表示存在连接房间u，v的通道，长度w。【输出格式】
第1行：一个整数，表示汇合房间的编号。若存在多个解，输出字典序最小的。
第2行：一个整数，表示三人到该房间距离之和。
【样例输入】
5 3 1 4 3 5 5 4 3 9 4 1 7 1 2 1
【样例输出】
4 16
【提示】
对于50%的数据：1≤N≤1,000。
对于100%的数据：1≤N≤20,000。 1≤A,B,C,u,v<=N且A,B,C不相等；u,v不相等。 1≤w≤1,000。