import deque def main(): # 读取输入 data = list(input().split()) n, m, s, t = map(in...

import deque def main(): # 读取输入 data = list(input().split()) n, m, s, t = map(int, data[:4]) # 构建邻接表和逆邻接表 graph = [[] for _ in range(n + 1)] reverse_graph = [[] for _ in range(n + 1)] idx = 4 for _ in range(m): u, v, w = map(int, data[idx:idx + 3]) idx += 3 graph[u].append((v, w)) reverse_graph[v].append((u, w)) # 1. 计算最早开始时间 TE (拓扑排序) indegree = [0] * (n + 1) for u in range(1, n + 1): for v, w in graph[u]: indegree[v] += 1 # 拓扑排序 queue = deque() TE = [0] * (n + 1) # 找到所有入度为0的点 for i in range(1, n + 1): if indegree[i] == 0: queue.append(i) topo_order = [] while queue: u = queue.popleft() topo_order.append(u) for v, w in graph[u]: if TE[v] < TE[u] + w: TE[v] = TE[u] + w indegree[v] -= 1 if indegree[v] == 0: queue.append(v) # 2. 计算最晚开始时间 TL TL = [float('inf')] * (n + 1) TL[t] = TE[t] # 逆拓扑排序 outdegree = [0] * (n + 1) for u in range(1, n + 1): outdegree[u] = len(graph[u]) # 从终点开始反向计算 reverse_topo = topo_order[::-1] for u in reverse_topo: for v, w in graph[u]: if TL[u] > TL[v] - w: TL[u] = TL[v] - w # 3. 计算缓冲时间 slack = [TL[i] - TE[i] for i in range(n + 1)] # 输出关键路径长度 print(TE[t]) # 输出每个顶点的TE, TL, 缓冲时间 for i in range(1, n + 1): print(f"{TE[i]} {TL[i]} {slack[i]}") # 4. 找出所有关键路径 critical_paths = [] def dfs(current, path, paths): if current == t: paths.append(path[:]) return for next_node, weight in graph[current]: # 如果是关键边 (TE[current] + weight == TE[next_node] 且 slack[current] == 0) if TE[current] + weight == TE[next_node] and slack[current] == 0 and slack[next_node] == 0: path.append(next_node) dfs(next_node, path, paths) path.pop() # 从起点开始DFS寻找所有关键路径 start_path = [s] dfs(s, start_path, critical_paths) # 排序关键路径：先按节点个数，再按字典序 critical_paths.sort(key=lambda x: (len(x), x)) # 输出所有关键路径 for path in critical_paths: print(" ".join(map(str, path))) if __name__ == "__main__": main()