网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO NOV07]奶牛接力
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | relays.in | 输出文件 | relays.out |
【题目描述】
FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点,自然是在牧场中现有的T(2 <= T <= 100)条跑道上。
农场上的跑道有一些交汇点,每条跑道都连结了两个不同的交汇点I1_i和I2_i(1 <= I1_i <= 1,000; 1 <= I2_i <= 1,000)。每个交汇点都是至少两条跑道的端点。奶牛们知道每条跑道的长度length_i(1 <= length_i <= 1,000),以及每条跑道连结的交汇点的编号。并且,没有哪两个交汇点由两条不同的跑道直接相连。你可以认为这些交汇点和跑道构成了一张图。
为了完成一场接力跑,所有N头奶牛在跑步开始之前都要站在某个交汇点上(有些交汇点上可能站着不只1头奶牛)。当然,她们的站位要保证她们能够将接力棒顺次传递,并且最后持棒的奶牛要停在预设的终点。
你的任务是,写一个程序,计算在接力跑的起点(S)和终点(E)确定的情况下,奶牛们跑步路径可能的最小总长度。显然,这条路径必须恰好经过N条跑道。
【输入格式】
第1行: 4个用空格隔开的整数:N,T,S,以及E
第2..T+1行: 第i+1为3个以空格隔开的整数:length_i,I1_i,以及I2_i,描述了第i条跑道。
【输出格式】
第1行: 输出1个正整数,表示起点为S、终点为E,并且恰好经过N条跑道的路径的最小长度
【样例输入】
2 6 6 4 11 4 6 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9
【样例输出】
10
【提示】
数据规模如下:
数据编号 | N | K | 数据编号 | N | K |
1 | 5 | 2 | 6 | 50 | 1000000 |
2 | 20 | 200000 | 7 | 50 | 1000000 |
3 | 100 | 5000 | 8 | 100 | 1000000 |
4 | 20 | 1000000 | 9 | 80 | 1000000 |
5 | 90 | 500000 | 10 | 80 | 1000000 |
数据保证一定存在符合题意的路径。
【来源】
USACO NOV07 Gold
POJ 3613 Cow Relays