P2901 [USACO08MAR]牛慢跑Cow Jogging

    • 123通过
    • 252提交
  • 题目提供者 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).

    贝西尝到了懒惰的恶果——为了减肥,她不得不决定每周花几次时间在牛棚和池塘之间慢跑。但贝西并不想太累,所以她打算只跑从牛棚到池塘的下坡路,然后再慢慢地从池塘走回牛棚。 

    同时,贝西也不想跑得太远,所以她只想沿着通向池塘的最短路径跑步。在牧场里,每条道路连接了两个结点(这些结点的编号为1到N,1≤N≤1000)。另外,如果X>?,说明结点X的地势要高于Y,所以下坡的道路是从X通向Y的,贝西所在牛棚的编号为N(最高点),池塘的编号为1(最低点)。 

    而然,一周之后,贝西对单调的路线厌倦了,她希望每天可以跑不同的路线,比如说,最好能有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: 复制
    1 
    2 
    2 
    3 
    6 
    7 
    -1 
    

    说明

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

    (5-4-3-2-1).

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。