SPFA 最短路算法练习题：城市传送系统

📝 题目描述

有一个包含 \(n\) 个城市的传送网络，每两个城市之间可能存在单向传送路径，每条路径都有传送的时间消耗。传送系统的设计允许某些城市之间没有直接路径，甚至可能存在负权路径，但不允许出现负环。

现在，你被要求从城市 \(1\) 出发，计算到所有城市的最短传送时间。

📥 输入格式

• 第一行包含两个整数 \(n\) 和 \(m\)（\(1 \le n \le 10^4，1 \le m \le 5×10^4\)），表示城市数量和路径数量。
• 接下来 \(m\) 行，每行三个整数 \(u, v, w\)，表示存在一条从城市 \(u\) 到城市 \(v\) 的单向路径，耗时为 \(w\)（\(-1000 \le w \le 1000\)）。

📤 输出格式

• 输出一行包含 \(n\) 个整数，第 \(i\) 个数表示从城市 \(1\) 到城市 \(i\) 的最短传送时间（城市编号从 \(1\) 到 \(n\)）。
• 如果无法到达某个城市，输出 "-1" 表示无法到达。

🎯 样例输入

5 6
1 2 2
1 3 5
2 3 1
2 4 2
3 5 -3
4 5 3

✅ 样例输出

0 2 3 4 0

💡 提示

• 城市编号从 1 开始。
• 该图中不包含负权环，SPFA 可以正确运行。
• 可以使用 SPFA / Bellman-Ford ）等最短路算法解答，但推荐使用 SPFA。