题目名称	1589. [USACO Feb14]路障
输入输出	`rblock.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2014-04-13加入
开放分组	全部用户
提交状态
分类标签	USACO 最短路
	分享题解

通过：45，提交：108，通过率：41.67%
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
sywgz	100	0.000 s	0.00 MiB	C++
宇战	100	0.000 s	0.00 MiB	C++
Youngsc	100	0.000 s	0.04 MiB	C++
Mealy	100	0.002 s	0.32 MiB	C++
confoo	100	0.008 s	0.71 MiB	C++
FF_Sky\|\|幻	100	0.008 s	1.58 MiB	C++
Satoshi	100	0.009 s	0.49 MiB	C++
Suke	100	0.009 s	0.89 MiB	C++
Miku_lyt	100	0.009 s	1.22 MiB	C++

本题关联比赛
20140414

关于路障的近10条评论(全部评论)
枚举最短路上的边，改变权值再做最短路更新答案 dij+heap ORZ lky 2014-09-11 19:52 6楼
不会堆优化！！ zgyzhaoguangyang 2014-04-14 17:19 5楼
貌似这题Dijkstra比SPFA快？给各位手打堆的犇跪了…… cstdio 2014-04-14 16:31 4楼
在堆down操作打错一个变量，以及只枚举最短路上的最大权值的边的情况下，还能过9个点。。无语 Suke 2014-04-14 15:02 3楼
堆打狗了。。。。。。 ◆半城烟沙灬為你打天下 2014-04-14 14:03 2楼
没有退队！！！！（ˇˍˇ）～耶稣 2014-04-14 12:02 1楼

1589. [USACO Feb14]路障

★★☆ 输入文件：rblock.in 输出文件：rblock.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

每天早晨醒来，FJ穿过农场从他家的谷仓。该农场有N个场（1≤n≤250），由M条双向通路的连接（1≤M＜＝25000），每一条通路都有一个长度。FJ的房子是在1场，谷仓在N场，两个场之间没有冗余通路，按一个适当的顺序沿路径走，可以前往任何场。当从一个场到另一个，FJ总是选择组成的路径序列的总长度最小通路通过。农夫约翰的奶牛，总是没有好起来，决定妨碍他的早上行程。他们计划建造一堆干草捆在一个农场上的通路上，这样会使其长度加倍。奶牛要选择，使他们的工作能最大限度地增加FJ从家里到谷仓的途径的距离。请帮助奶牛决定如何能延长FJ的路线。

【输入格式】

第1行有2个整数：N,M；

接下来有M行，也就是第2--M+1行，行j+1描述了三个用空格隔开的整数,表示双向通路：a_j b_j

l_j，在a_j和b_j是指数范围在1—n表示的通路，和l_j的路径长度（范围在1……1000000）。

【输出格式】

第1行，有一个数，表示最大限度地增加量的值，加倍的单一通道的长度可能影响在计算最短路径的总长度

【样例输入】

【样例输出】

【提示】

输出解释：

有5个场和7个途径。目前，从家的最短路径（1场）到谷仓（5场）是1-3-4-5总长度1 + 3 + 2 =

6。如果奶牛修改双长度的是3场到4场（其长度从3增加到6），然后FJ的最短路径是现在1-3-5，总长度1 + 7 =

8，比以前的最短路径长度更大，增加值为2。