📘 Bellman-Ford 模板题

🧾 题目描述

给定一个 有向图，图中可能存在 负权边，也可能 存在负权环。

你的任务是从给定的起点出发，计算从 起点 到所有其他点的最短距离。

📥 输入格式

• 第一行三个整数 n 和 m,s（1 ≤ n ≤ 500, 0 ≤ m ≤ 10^4,1 ≤ s ≤ n），表示图的点数和边数。
• 接下来的 m 行，每行三个整数 u, v, w，表示一条从 u 到 v 的有向边，权重为 w，-10000 ≤ w ≤ 10000。

📤 输出格式

• 输出 n 行，分别表示从点 s 到 1, 2, ..., n 的最短路径长度。
• 如果某个点无法到达，输出 -1。
• 如果存在负环的话，请输出 minus cycle found

📚 输入样例

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

📘 输出样例

0
2
4
1
5

💡 提示说明

• 这道题适合使用 Bellman-Ford 算法或其优化版本 SPFA。
• 注意初始值设置、无法到达时输出 -1。