题目描述

有边数限制的最短路

JAVA 代码

//bellman_ford算法的时间复杂度为O(n∗mn∗m)，这里n为点数，m为边数
import java.util.*;
import java.io.*;

class Node{
    int a,b,c;
    Node(int a,int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

class Main{
    static int N = 10010;
    static Node[] edge = new Node[N];
    static int[] d = new int[N];
    static int n,m,k, INF = 0x3f3f3f3f;

    static int bellman_ford(){
        Arrays.fill(d, INF);
        d[1] = 0;

        //循环k次
        for(int i =0; i<k; i++){
            //对d数组做一次备份
            int[] copy = Arrays.copyOf(d,N);
            for(int j=0; j<m;j++){
                Node cur = edge[j];
                int a = cur.a;
                int b = cur.b;
                int c = cur.c;
                if(d[b] > copy[a]+c){
                    d[b] = copy[a] + c;
                }
            }
        }
        //有负权, 可能会小一些些.
        if(d[n]>= INF/2) return -1;
        return d[n];
    }

    public static void main(String args[])throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String [] s = in.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);

        for(int i=0; i<m; i++){
            s = in.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            edge[i] = new Node(a,b,c);
        }
        int t = bellman_ford();
        if(t==-1) System.out.println("impossible");
        else System.out.println(t);
    }
}