P2934 [USACO09JAN]安全出行Safe Travel

    • 252通过
    • 858提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 并查集 最短路 最近公共祖先,LCA USACO 2009 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Gremlins have infested the farm. These nasty, ugly fairy-like

    creatures thwart the cows as each one walks from the barn (conveniently located at pasture_1) to the other fields, with cow_i traveling to from pasture_1 to pasture_i. Each gremlin is personalized and knows the quickest path that cow_i normally takes to pasture_i. Gremlin_i waits for cow_i in the middle of the final cowpath of the quickest route to pasture_i, hoping to harass cow_i.

    Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture_1 (the barn) to pasture_i.

    Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow_i that avoid gremlin_i who is located on the final cowpath of the quickest route from pasture_1 to

    pasture_i.

    As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a_i (1 <= a_i <= N) and b_i (1 <= b_i <= N) and requires t_i (1 <= t_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a_i != b_i). Best of all, the shortest path regularly taken by cow_i from pasture_1 to pasture_i is unique in all the test data supplied to your program.

    By way of example, consider these pastures, cowpaths, and [times]:

    1--[2]--2-------+ 
    |       |       | 
    [2]     [1]     [3] 
    |       |       | 
    +-------3--[4]--4
    TRAVEL     BEST ROUTE   BEST TIME   LAST PATH 
    p_1 to p_2       1->2          2         1->2 
    p_1 to p_3       1->3          2         1->3 
    p_1 to p_4      1->2->4        5         2->4 

    When gremlins are present:

    TRAVEL     BEST ROUTE   BEST TIME    AVOID 
    p_1 to p_2     1->3->2         3         1->2 
    p_1 to p_3     1->2->3         3         1->3 
    p_1 to p_4     1->3->4         6         2->4 

    For 20% of the test data, N <= 200.

    For 50% of the test data, N <= 3000.

    TIME LIMIT: 3 Seconds

    MEMORY LIMIT: 64 MB

    Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的 地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它 们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找 一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最 短路经的长度.

    和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到 达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i (1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过. 没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛 棚_i的最短路经是唯一的.

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and M

    * Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i

    输出格式:

    * Lines 1..N-1: Line i contains the smallest time required to travel from pasture_1 to pasture_i+1 while avoiding the final cowpath of the shortest path from pasture_1 to pasture_i+1. If no such path exists from pasture_1 to pasture_i+1, output -1 alone on the line.

    输入输出样例

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

    说明

    感谢 karlven 提供翻译。

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