本文共 1949 字，大约阅读时间需要 6 分钟。

时间复杂度：O(nm)

给定一个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≤n,k≤500,

输入样例：

3 3 11 2 12 3 11 3 3

输出样例：

3

BellManFord思想：

把所有的边存起来，然后遍历所有的边，更新该边首节点到该边尾节点的距离，因为有边数限制，因此要保存上一次的距离数组dist为backup，用backup去更新距离。需要多少个边，循环多少次。

注：每轮要更新dist距离数组  dist[b] = Math.min(dist[b], backup[a] + w);

import java.io.*;import java.lang.*;import java.util.*;class Main{    static int n = 0, m = 0, k = 0;    static int N = 10010;    static int[][] edges = new int[N][3];    static int[] dist = new int[510];    static int[] backup = new int[510];    static int bellmanFord(){        Arrays.fill(dist, 0x3f3f3f3f);        dist[1] = 0;        for(int i = 0; i < k; ++i){            backup = Arrays.copyOf(dist, N);            for(int j = 1; j <= m; ++j){                int a = edges[j][0], b = edges[j][1], w = edges[j][2];                dist[b] = Math.min(dist[b], backup[a] + w);            }        }        if(dist[n] >= 0x3f3f3f3f / 2)return -1;        return dist[n];            }        public static void main(String[] args)throws Exception{        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        String[] params = buf.readLine().split(" ");        n = Integer.valueOf(params[0]);        m = Integer.valueOf(params[1]);        k = Integer.valueOf(params[2]);        for(int i = 1; i <= m; ++i){            String[] info = buf.readLine().split(" ");            edges[i][0] = Integer.valueOf(info[0]);//入            edges[i][1] = Integer.valueOf(info[1]);//出            edges[i][2] = Integer.valueOf(info[2]);//权值        }        int cond = bellmanFord();        if(cond != -1){            System.out.print(cond);        }else{            System.out.print("impossible");        }            }}