Preparing NOJ
当进行软件开发时,我们需要建立开发项目的里程碑,才能够知道本身的进度。这些里程碑类似于我们在旅程中的路标,让我们可以清楚地知道目前所在,离开目的地有多远,让我们能估算何时才能够完成软件。里程碑之间是软件开发活动,需要耗费一定时间。软件项目管理的一个重要任务是监控关键的里程碑、关键的软件开发活动,这些里程碑不能提前,也不能拖后,否则影响到整个软件开发过程。现在假设有n个里程碑(0号里程碑为软件开发启动点,n-1号里程碑为软件开发过程结束点),这些里程碑之间有m个软件开发活动,请找出关键的里程碑。
第一行是一个正整数:测试用例数目,最多为100。之后,每个测试用例包括多行:
l 第1行给出两个整数(空格分割),第一个整数表示里程碑数n,2≤n≤200,第二个整数表示软件开发活动数m,0≤m≤20100。
l m行,每行三个整数(空格分割),前两个整数表示两个里程碑,第三个整数表示上述两个里程碑之间的软件开发活动需要花费的时间t,里程碑分别用0、1、…,n-1等序号表示,1≤t≤100。
对于每个测试用例:
l 按照软件开发顺序给出关键的里程碑(用序号表示)
注意:输出部分的结尾要求包含一个多余的空行。
2
2 1
0 1 1
3 3
0 1 2
1 2 3
0 2 8
0 1
0 2
本题由旧版NOJ导入,来源:算法与数据结构设计2009