题目描述

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    static int N;
    static int n, m, k;
    static Edge[] edges;
    static int[] dist, backup;
    static final int INF = 0x3f3f3f3f;
    static class Edge{
        int a, b, w;
        Edge(int a, int b, int w){
            this.a = a; this.b = b; this.w = w;
        }
    }

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

        edges = new Edge[m];
        dist = new int[n+1];
        backup = new int[n+1];

        for(int i = 0; i < m; i++){
            String[] s1 = cin.readLine().split("\\s+");
            int a = Integer.valueOf(s1[0]);
            int b = Integer.valueOf(s1[1]);
            int w = Integer.valueOf(s1[2]);
            edges[i] = new Edge(a, b, w);
        }

        int t = BF();
        if(t == -1) System.out.println("impossible");
        else System.out.println(t);
    }

    static int BF(){
        // 初始化距离
        Arrays.fill(dist, INF);
        dist[1] = 0;
        for(int i = 0; i < k; ++i){
            backup = dist.clone();
            for(int j = 0; j < m; j++){
                int a = edges[j].a;
                int b = edges[j].b;
                int w = edges[j].w;
                 dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if(dist[n] > INF / 2)   return -1;
        return dist[n];
    }

}