
 442通过
 920提交
 题目提供者 FarmerJohn2
 评测方式 云端评测
 标签 动态规划,动规,dp 最短路 矩阵乘法 USACO 2007 高性能
 难度 提高+/省选
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.
Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.
To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cowbycow and end up at the proper finishing place.
Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.
给出一张无向连通图，求S到E经过k条边的最短路。
输入输出格式
输入格式：* Line 1: Four spaceseparated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three spaceseparated integers: lengthi , I1i , and I2i
输出格式：* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.