853. 有边数限制的最短路（Bellman-ford算法模板）

给定一个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≤500
1≤m≤10000
任意边长的绝对值不超过10000。

输入样例：

输出样例：

3

代码：

//可能出现负权回路，所以最短路径不一定存在

import java.util.Arrays;

import java.util.Scanner;

class Node{

        int a;

        int b;

        int w;

}

public class Main{

        static final int N=505, INF=(int)1e9+5;

        static int n,m,k;

        static int dis[]=new int[N];

        static int backup[]=new int[N];//使用上一次更新的状态，避免串联更新，eg：更新过1到2距离，然后利用另一个条件又更新了一遍

        static Node node[]=new Node[10005];

        static int bellman_ford(){

                Arrays.fill(dis, INF);

                dis[1]=0;

                for(int i=1;i<=k;i++){//k次更新，说明a到b最多不超过k条边

                        backup=Arrays.copyOf(dis, n+1);

                        for(int j=0;j<m;j++){//更新每条边

                                int a=node[j].a;

                                int b=node[j].b;

                                int w=node[j].w;

                                dis[b]=Math.min(dis[b],backup[a]+w);//松弛操作

                        }

                }

                if(dis[n]>INF/2) return -1;//因为可能出现负权边，所以就算dis[n]不可达，但可能出现dis[n]<INF

                else return dis[n];

        }

         public static void main(String[] args) {

                 Scanner scan=new Scanner(System.in);

                 n=scan.nextInt();

                 m=scan.nextInt();

                 k=scan.nextInt();

                 for(int i=0;i<m;i++){

                         node[i]=new Node();

                         node[i].a=scan.nextInt();

                         node[i].b=scan.nextInt();

                         node[i].w=scan.nextInt();

                 }

                 int ans=bellman_ford();

                 if(ans==-1)  System.out.println("impossible");

                 else System.out.println(ans);

        }

 }

巴特西