问题 BA: 图-节点的最早发生时间
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:617
解决:772
题目描述
下图是一个有向无环图,节点内的数字表示该节点的序号,节点之间的连接线表示节点之间的连接方式,连接线上方的黑色数字表示该连接线的权重。
最早发生时间:从前往后,前驱节点到当前节点所需时间,取最大值
本题要求:求出有向无环图中每一个节点的最早发生时间(示例图中每一个节点的最早发生时间以节点上方的黄色数字标出)
最早发生时间:从前往后,前驱节点到当前节点所需时间,取最大值
本题要求:求出有向无环图中每一个节点的最早发生时间(示例图中每一个节点的最早发生时间以节点上方的黄色数字标出)
输入
第一行为2个正整数m和n,分别表示有向无环图的节点个数和边的数量。
接下来n行,代表n条边。分别是起点、终点、权重,以空格分隔。
(m<50,n<100)
接下来n行,代表n条边。分别是起点、终点、权重,以空格分隔。
(m<50,n<100)
输出
按行输出有向无环图中每一个节点最早发生时间,按照节点的序号从小到大输出。
如样例中,0、1、2、3、4号节点的最早发生时间分别是0、3、3、7、11。
则按行输出0、3、3、7、11。
如样例中,0、1、2、3、4号节点的最早发生时间分别是0、3、3、7、11。
则按行输出0、3、3、7、11。
样例输入 复制
5 6
0 1 3
0 2 3
1 3 2
2 3 4
2 4 4
3 4 4
样例输出 复制
0
3
3
7
11