比赛场次 230
比赛名称 20140414
比赛状态 已结束比赛成绩
开始时间 2014-04-14 08:00:00
结束时间 2014-04-14 11:30:00
开放分组 全部用户
注释介绍 usaco 2014 2月月赛金组题
题目名称 路障
输入输出 rblock.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarLuciFer_T-J AAAAAAAAAA 0.008 s 1.27 MiB 100
GravatarFF_Sky||幻 AAAAAAAAAA 0.011 s 1.58 MiB 100
Gravatarcstdio AAAAAAAAAA 0.013 s 0.57 MiB 100
GravatarDijkstra AAAAAAAAAA 0.013 s 0.80 MiB 100
Gravatarzgyzhaoguangyang AAAAAAAAAA 0.047 s 0.74 MiB 100
GravatarOI永别 AAAAAAAAAA 1.150 s 1.70 MiB 100
GravatarSuke AAAAAAAWAA 0.007 s 1.08 MiB 90
GravatarHZOI_lhy111 AAAAAAAATA 1.748 s 1.46 MiB 90
GravatarMiku_lyt AAAAAAAWWA 0.008 s 1.12 MiB 80
Gravatar◆半城烟沙灬為你打天下 AAAAAAAWWA 0.017 s 1.35 MiB 80
Gravatar(ˇˍˇ) ~耶稣 AAAAAAWWWA 0.801 s 1.63 MiB 70
Gravatarhzoi_zyl AAAAWWWWWA 0.011 s 0.52 MiB 50
GravatarCirno AAAAWWWWWA 0.020 s 0.55 MiB 50
Gravatardigital-T AWWAWAWWWW 0.009 s 0.32 MiB 30
Gravatar隨風巽 AEWWWWWWWA 0.098 s 0.32 MiB 20
Gravatarys WWWWWTWTWW 2.012 s 1.47 MiB 0

路障

★★☆   输入文件: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
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

【样例输出】

2

【提示】

输出解释:

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

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

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