#CW7. 最长旅程(journey)
最长旅程(journey)
题目描述
有一张包含 个点和 条有向边的图。每条边都有一个正整数标签。
从某个点出发,可以沿有向边不断前进。若依次经过的点为
则称这是一段长度为 的行程,也就是连续走过了 条边。
保证这张图中不存在可以无限进行的行程,从任意点出发都只能走有限条边。
对于每个点,考虑从它出发能够达到的最大行程长度。如果存在多种同样长的方案,则比较它们经过的边标签序列,选择其中字典序最小的一种。
对于每个起点,请输出所选行程的长度,以及该行程中所有边的标签之和。
这里,两个等长序列的字典序比较方式为:找到它们第一个不同的位置,当前位置数值更小的序列更小。
输入格式
第一行包含两个整数 。
接下来 行,每行包含三个整数 ,表示存在一条从城市 指向城市 的有向边,其标签为 ,其中 。
保证任意两个城市之间至多存在一条有向边,并且图中不存在无限长的行程。
输出格式
输出 行。
第 行输出两个整数,分别表示从城市 出发所选择行程的:
- 长度;
- 所有边标签的总和。
样例 1 输入
4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10
样例 1 输出
0 0
1 10
1 10
2 20
样例 2 输入
4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 1
样例 2 输出
0 0
1 10
1 5
2 7
数据范围
对于所有测试数据,保证:,,,。
| 测试点 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| 所有 全部相等 | |||
| 所有 全部互不相同 | |||
| 无 |