logo AlgoBeat OnlineJudge
登录 注册

#101598. [BZOJ 1598] [Usaco2008 Mar]牛跑步

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Bessie 准备用从牛棚跑到池塘的方法来锻炼。但是因为她懒,她只准备沿着下坡的路跑到池塘,然后走回牛棚。Bessie 也不想跑得太远,所以她想走最短的路径。农场上一共有 条路, 每条路连接两个地点,共有 个地点。更方便的是,如果 ,则地点 的高度大于地点 的高度。地点 是 Bessie 的牛棚; 地点 是池塘。很快,Bessie 厌倦了一直走同一条路。所以她想走不同的路,更明确地讲,她想找出 条不同的路径。为了避免过度劳累,她想使这 条路经为最短的 条路径。请帮助 Bessie 找出这 条最短路径的长度。

输入格式

  • 行: 个数:

  • 行:第 行包含3个数 ,表示一条下坡的路.

输出格式

  • 行:第 行包含第 条最短路径的长度。如果这样的路径不存在,输出 。如果多条路径有同样的长度,请将这些长度逐一列出。

样例

样例输入 #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

数据范围与提示

对于 的数据,。 路径分别为

Usaco 2008 Mar Gold