比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
LuciFer_T-J | AAAAAAAAAA | 0.008 s | 1.27 MiB | 100 |
FF_Sky||幻 | AAAAAAAAAA | 0.011 s | 1.58 MiB | 100 |
cstdio | AAAAAAAAAA | 0.013 s | 0.57 MiB | 100 |
Dijkstra | AAAAAAAAAA | 0.013 s | 0.80 MiB | 100 |
zgyzhaoguangyang | AAAAAAAAAA | 0.047 s | 0.74 MiB | 100 |
OI永别 | AAAAAAAAAA | 1.150 s | 1.70 MiB | 100 |
Suke | AAAAAAAWAA | 0.007 s | 1.08 MiB | 90 |
HZOI_lhy111 | AAAAAAAATA | 1.748 s | 1.46 MiB | 90 |
Miku_lyt | AAAAAAAWWA | 0.008 s | 1.12 MiB | 80 |
◆半城烟沙灬為你打天下 | AAAAAAAWWA | 0.017 s | 1.35 MiB | 80 |
(ˇˍˇ) ~耶稣 | AAAAAAWWWA | 0.801 s | 1.63 MiB | 70 |
hzoi_zyl | AAAAWWWWWA | 0.011 s | 0.52 MiB | 50 |
Cirno | AAAAWWWWWA | 0.020 s | 0.55 MiB | 50 |
digital-T | AWWAWAWWWW | 0.009 s | 0.32 MiB | 30 |
隨風巽 | AEWWWWWWWA | 0.098 s | 0.32 MiB | 20 |
ys | WWWWWTWTWW | 2.012 s | 1.47 MiB | 0 |
每天早晨醒来,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。