TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1614
  • 题目
  • P1614【USACO 2009 JAN GOLD】安全路径
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    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的最短路经是唯一的。
    以下是一个牛棚,牛路和时间的例子:

    输入格式

    第一行:两个空格分开的数N和M;
    第2..M+1行:三个空格分开的数a_i, b_i,和t_i

    输出格式

    第1..N-1行:第i行包含一个数,从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间。如果这样的路经不存在,输出-1。

    样例输入

    4 5
    1 2 2
    1 3 2
    3 4 4
    3 2 1
    2 4 3

    样例输出

    3
    3
    6

    提示

    【数据范围】
    20%的数据满足,N<=200;
    50%的数据满足,N<=3000
    100%的数据满足,N<=100,000


    来源  USACO 2009 JAN GOLD