bellman_ford算法用于解决：　

什么是bellman - ford算法？

Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)　　

时间复杂度为O(mn)

bellman - ford算法的具体步骤

for k次for 所有边 a,b,w (松弛操作)dist[b] = min(dist[b],back[a] + w)

注意：

模板题：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

1≤n,k≤5001≤m≤10000,任意边长的绝对值不超过 10000。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

1≤n≤5001≤m≤10^5图中涉及边长均不超过10000。

用bellmanford算法求最短路的时候，就不需要backup备份了，注意。