关键通路（2022秋）

题目描述

观赛完运动会之后，花叶现在已经在钢条厂上班，但是钢条厂繁杂的流水线让花叶很是苦恼，他希望你来帮他求一下关键通路！

花叶其实在瞬间就计算完毕了，但是他不确定是不是正确的，于是他希望你也帮忙计算一下关键通路是什么。

形式化来说，给一个 $n$ 个点 $m$ 条边的带权有向图，求点 $s$ 到点 $t$ 的关键通路。

输入

第一行四个正整数 $n,m,s,t$，其中 $1 \leq n \leq 15$，$1 \le s,t \le n$，含义如题目所示。

接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$，其中$1 \le u_i, v_i \le n$，$1 \leq w_i \leq 10^3$，表示第 $i$ 条边 $(u_i, v_i)$ 的权值为 $w_i$。

输出

第一行输出关键通路的长度；

第二行到第 $n+1$ 行输出每一个顶点的 TE, TL 和缓冲时间；

最后一行按Hint中所给格式，输出所有的关键通路。（若有多条，则根据关键通路中节点的个数排序进行输出，长度相同则按字典序排）

输入样例

9 15 1 9
1 2 3
1 3 2
1 4 4
2 5 4
2 3 0
3 5 4
3 6 4
3 4 2
4 7 5
5 9 6
5 7 3
5 6 0
6 8 3
8 9 1
7 8 1

输出样例

Dis=13
Node 1: TE=   0  TL=   0  TL-TE= 0
Node 2: TE=   3  TL=   3  TL-TE= 0
Node 3: TE=   3  TL=   3  TL-TE= 0
Node 4: TE=   5  TL=   6  TL-TE= 1
Node 5: TE=   7  TL=   7  TL-TE= 0
Node 6: TE=   7  TL=   9  TL-TE= 2
Node 7: TE=  10  TL=  11  TL-TE= 1
Node 8: TE=  11  TL=  12  TL-TE= 1
Node 9: TE=  13  TL=  13  TL-TE= 0
[[1, 2, 5, 9], [1, 2, 3, 5, 9]]

Hint

本题目仅支持Python，想通过默认c语言提交的同学注意了哦。

得0.66的同学注意当长度相等时的排序问题

建立"数组"(其实这里是List列表数据类型)：

array = [value]*n  
array = [[value for i in range(n)] for j in range(m)] # 二维

格式化输出：

print("Dis=", distance[end], sep="")  
print("Node",i, end="")  
print(": TE= %3d" % (te[i]), sep="", end=" ")  
print(" TL= %3d" % (tl[i]), sep="", end=" ")  
print(" TL-TE= ", tl[i] - te[i], sep="")  

关键通路输出：

print(array)
# 如果你把所有的路径都存在一个List里，可以直接这样print，这里的array为二维的

对多条通路进行排序：

sorted(all_paths, key = len)