bzoj#P1576. [USACO09JAN]Safe Travel G

[USACO09JAN]Safe Travel G

题目描述

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

和以往一样,农场,上的 mm 条双向牛路编号为 11mm 并且能让所有牛到达它们的目的地,nn 个牛棚,牛路 ii 连接牛棚 aia_ibib_i 并且需要时间 tit_i 通过。没有两条牛路连接同样的牛棚,所有牛路满足 aibia_i\not =b_i。在所有数据中,牛 ii 使用的牛棚 11 到牛棚 ii 的最短路经是唯一的。

以下是一个牛棚,牛路和时间的例子:

行程 最佳路径 最佳时间 最后牛路
p1p_1p2p_2 121→2 22 121→2
p1p_1p3p_3 131→3 131→3
p1p_1p4p_4 1241→2→4 55 242→4

当精灵进入农场后:

行程 最佳路径 最佳时间 避免
p1p_1p2p_2 1321→3→2 33 121→2
p1p_1p3p_3 1231→2→3 131→3
p1p_1p4p_4 1341→3→4 66 242→4

输入格式

第一行:两个空格分开的数,nnmm

2m+12\sim m+1 行:三个空格分开的数 ai,bi,tia_i,b_i,t_i

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,2m2×1052\leq m\leq 2\times 10^53n1×1053\leq n\leq 1\times 10^51ai,bin1\leq a_i,b_i\leq n1ti10001≤t_i≤1000

题目来源

Usaco 2009 Jan Gold