P2901 [USACO08MAR]牛慢跑Cow Jogging

    • 213通过
    • 473提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 广度优先搜索,BFS 递推 USACO 2008
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示


    Bessie has taken heed of the evils of sloth and has decided to get fit by jogging from the barn to the pond several times a week. She doesn't want to work too hard, of course, so she only plans to jog downhill to the pond and then amble back to the barn at her leisure.

    Bessie also doesn't want to jog any too far either, so she generally takes the shortest sequence of cow paths to get to the pond. Each of the M (1 <= M <= 10,000) cow paths connects two pastures

    conveniently numbered 1..N (1 <= N <= 1000). Even more conveniently, the pastures are numbered such that if X>Y then the cow path from pasture X to pasture Y runs downhill. Pasture N is the barn (at the top of the hill) and pasture 1 is the pond (at the bottom).

    Just a week into her regimen, Bessie has begun to tire of always taking the same route to get to the pond. She would like to vary her route by taking different cow paths on different days. Specifically, Bessie would like to take exactly K (1 <= K <= 100) different routes for variety. To avoid too much exertion, she wants these to be the K shortest routes from the barn to the pond. Two routes are considered different if they comprise different sequences of cow paths.

    Help Bessie determine how strenuous her workout will be by determining the lengths of each of the K shortest routes on the network of pastures. You will be supplied a list of downhill cow paths from X_i to Y_i along with the cow path's length: (X_i, Y_i, D_i) where (1 <= Y_i < X_i; Y_i < X_i <= N). Cowpath i has length D_i (1 <= D_i <= 1,000,000).



    而然,一周之后,贝西对单调的路线厌倦了,她希望每天可以跑不同的路线,比如说,最好能有K (1≤K≤100)种不同的选择。为了不至于跑得太累,她希望这K条路径是从牛棚到池塘的最短的K条路径。 

    请帮助贝西算算她的运动量,即找出网络里最短的K条路径的长度。假设每条道路用(Xi,Yi,Di)表示,其中1≤Yi<Xi≤N,表示这条道路从Xi出发到Yi,其长度为Di (1≤Di≤1,000,000)。



    * Line 1: Three space-separated integers: N, M, and K

    * Lines 2..M+1: Line i+1 describes a downhill cow path using three space-separated integers: X_i, Y_i, and D_i


    * Lines 1..K: Line i contains the length of the i-th shortest route or -1 if no such route exists. If a shortest route length occurs multiple times, be sure to list it multiple times in the output.


    输入样例#1: 复制
    5 8 7 
    5 4 1 
    5 3 1 
    5 2 1 
    5 1 1 
    4 3 4 
    3 1 1 
    3 2 1 
    2 1 1 
    输出样例#1: 复制


    The routes are (5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),