bzoj#P1576. [USACO09JAN]Safe Travel G
[USACO09JAN]Safe Travel G
题目描述
精灵最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚 )走到别的牛棚(牛 的目的地是牛棚 )。每一个精灵只认识牛 并且知道牛 一般走到牛棚的最短路经。所以它们在牛 到牛棚 之前的最后一条牛路上等牛 。当然,牛不愿意遇到精灵,所以准备找一条稍微不同的路经从牛棚 走到牛棚 。所以,请你为每一头牛i找出避免精灵的最短路经的长度。
和以往一样,农场,上的 条双向牛路编号为 到 并且能让所有牛到达它们的目的地, 个牛棚,牛路 连接牛棚 和 并且需要时间 通过。没有两条牛路连接同样的牛棚,所有牛路满足 。在所有数据中,牛 使用的牛棚 到牛棚 的最短路经是唯一的。
以下是一个牛棚,牛路和时间的例子:
行程 | 最佳路径 | 最佳时间 | 最后牛路 |
---|---|---|---|
到 | |||
到 | |||
到 |
当精灵进入农场后:
行程 | 最佳路径 | 最佳时间 | 避免 |
---|---|---|---|
到 | |||
到 | |||
到 |
输入格式
第一行:两个空格分开的数, 和 。
第 行:三个空格分开的数 。
输出格式
第 行:第 行包含一个数:从牛棚 到牛棚 并且避免从牛棚 到牛棚 最短路经上最后一条牛路的最少的时间。如果这样的路经不存在,输出 。
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
3
3
6
数据规模与约定
对于 的数据,,,,。
题目来源
Usaco 2009 Jan Gold