| 题目名称 | 2109. [NOIP 2015]运输计划 |
|---|---|
| 输入输出 | transport.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2015-11-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：259， 提交：1385， 通过率：18.7% | ||||
 BaDBoY |
100 | 0.335 s | 27.73 MiB | C++ |
 天亮说晚安· |
100 | 0.418 s | 24.38 MiB | C++ |
|
BaDBoY |
100 | 0.508 s | 14.34 MiB | C++ |
 zjh |
100 | 0.619 s | 22.64 MiB | C++ |
 Tiny |
100 | 0.712 s | 122.03 MiB | C++ |
 szzy |
100 | 0.736 s | 20.89 MiB | C++ |
 Hallmeow |
100 | 0.736 s | 39.57 MiB | C++ |
 wumingshi |
100 | 0.741 s | 20.89 MiB | C++ |
 test |
100 | 0.761 s | 23.20 MiB | C++ |
|
test |
100 | 0.781 s | 23.20 MiB | C++ |
| 本题关联比赛 | |||
| 假期找点事儿做题吧 | |||
| 近期练习题回顾 | |||
| 关于 运输计划 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
++和--写反，果断WA0 | ||||
|
@Hzoi__goodboy
不要脸  ~玖湫~
2017-11-09 12:05
47楼
| ||||
|
最后一个点实在是太凶残了QAQ
只能打表T-T 待我来填此坑（先撑过NOIP2017再说） Hallmeow
2017-11-06 12:49
46楼
| ||||
|
20170713：最后一个点太凶残了，卡常卡不过去就打了个表，结果成了rank1，我也是醉了。。。
20171103UPD：终于不用打表AC了。。顺便吐槽：经过本zz的多次测试，不加任何优化时间效率是最高的。。。 如果有人有好的优化方法可以告诉我。。 | ||||
|
回复 @ワンパンマン :
可是这两个值明明相等，都是-2147483647  _Itachi
2017-10-29 11:42
44楼
| ||||
|
mdzz，我的最小值本来定的-(1<<31)+1，结果w一个点，换成-0x7fffffff才A，注意啊各位！！！
| ||||
|
vector果然太慢，于是我果断选择打表(逃)。
 Shirry
2017-10-12 17:51
42楼
| ||||
|
咦哲学符号哪里去了……
 HZOI_蒟蒻一只
2017-10-07 10:21
41楼
| ||||
|
学会树剖了哈哈
| ||||
|
不过不打表不剪枝也能无压力跑过。。。
| ||||
WxjianF019
サイタマ 
CSU_Turkey
Imone NOI2018Au【题目描述】
公元 $ 2044 $ 年，人类进入了宇宙纪元。
L 国有 $ n $ 个星球，还有 $ n - 1 $ 条双向航道，每条航道建立在两个星球之间，这 $ n - 1 $ 条航道连通了 $ L $ 国的所有星球。
小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $ u_i $ 号星球沿最快的宇航路径飞行到 $ v_i $ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $ j $，任意飞船驶过它所花费的时间为 $ t_j $，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新，L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 $ m $ 个运输计划。在虫洞建设完成后，这 $ m $ 个运输计划会同时开始，所有飞船一起出发。当这 $ m $ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?
【输入格式】
第一行包括两个正整数 $ n $、$ m $，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $ 1 $ 到 $ n $ 编号。
接下来 $ n - 1 $ 行描述航道的建设情况，其中第 $ i $ 行包含三个整数 $ a_i $、$ b_i $ 和 $ t_i $，表示第 $ i $ 条双向航道修建在 $ a_i $ 与 $ b_i $ 两个星球之间，任意飞船驶过它所花费的时间为 $ t_i $。 接下来 $ m $ 行描述运输计划的情况，其中第 $ j $ 行包含两个正整数 $ u_j $ 和 $ v_j $，表示第 $ j $ 个运输计划是从 $ u_j $ 号星球飞往 $ v_j $ 号星球。
【输出格式】
共 $ 1 $ 行，包含 $ 1 $ 个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
【样例输入】
6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5
【样例输出】
11
【提示】
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
【来源】
NOIP 2015 Day 2 Task 3