动态规划
相当于
dp[i][j]代表从i到j的最短路径
这时候的最短路径 仅仅是初始化的时候 点与点之间的直接相连。
每次向其中 增加一个中间节点
所有节点指点的dp状态都会随之改变，即每增加一个节点 所有的dp[i][j]都有可能更新
但是不论增加的节点的顺序是什么，最终的结果都是一样的
即增加 k1,k2 和 增加 k2,k1 最终结果一样

因此一共N个点 依次进行添加
其中 每次增加一个点都需要更新整个dp
所以是O（n^3）

我们从动态规划的角度考虑，解动态规划题目的重点就是合理的定义状态，划分阶段，我们定义 f[k][i][j] 为经过前k的节点，从i到j所能得到的最短路径，f[k][i][j]可以从f[k-1][i][j]转移过来，即不经过第k个节点，也可以从f[k-1][i][k]+f[k-1][k][j]转移过来，即经过第k个节点。

观察一下这个状态的定义，满足不满足最优子结构和无后效性原则。

最优子结构
图结构中一个显而易见的定理：

最短路径的子路径仍然是最短路径, 这个定理显而易见，比如一条从a到e的最短路a->b->c->d->e 那么 a->b->c 一定是a到c的最短路c->d->e一定是c到e的最短路，反过来，如果说一条最短路必须要经过点k，那么i->k的最短路加上k->j的最短路一定是i->j 经过k的最短路，因此，最优子结构可以保证。

无后效性
状态f[k][i][j]由f[k-1][i][j]，f[k-1][i,k] 以及f[k-1][k][j]转移过来，很容易可以看出，f[k] 的状态完全由f[k-1]转移过来，只要我们把k放倒最外层循环中，就能保证无后效性。

满足以上两个要求，我们即证明了Floyd算法是正确的。

我们最后得出一个状态转移方程：f[k][i][j] = min(f[k-1][i][k],f[k-1][i][k],f[k-1][k][j]) ，可以观察到，这个三维的状态转移方程可以使用滚动数组进行优化。

K 为什么要放在最外层
采用动态规划思想，f[k][i][j] 表示 i 和 j 之间可以通过编号为 1…k 的节点的最短路径。

f[0][i][j] 初值为原图的邻接矩阵。

f[k][i][j]则可以从f[k-1][i][j]转移来，表示 i 到 j 不经过 k 这个节点。

也可以 f[k-1][i][k]+f[k-1][k][j] 从转移过来，表示经过 k 这个点。

意思即 f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])

然后你就会发现 f 最外层一维空间可以省略，因为 f[k] 只与 f[k-1] 有关。

Floyd算法的本质是DP，而k是DP的阶段，因此要写最外面。

import java.util.Scanner;
import java.util.*;

public class Main{
    public static void main(String[] args){
        /***
         Scanner in = new Scanner(System.in);
         int length = in.nextInt();
         ArrayList<Integer> items = new ArrayList<Integer>();
         while(in.hasNext()){
         items.add(in.nextInt());
         }
         items.sort(Comparator.naturalOrder());
         Integer[] array = items.toArray(new Integer[0]);
         ***/

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int K = in.nextInt();
        int M = in.nextInt();

        int[][] map = new int[N][N];

        for(int i=0;i<n;i++){
            Arrays.fill(map[i],Integer.MAX_VALUE);
        }
        for(int i=0;i<n;i++){
            map[i][i] = 0;
        }
        for(int i =0; i<M;i++){
            int i = in.nextInt();
            int j = in.nextInt();
            int cost = in.nextInt();
            map[i][j] = cost;
        }

        //----------------------------------------
        int res = floyd(map,K);
        System.out.println(res);
    }
    public static int floyd(int[][] map, int K) {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }
        }
        int max_ = Integer.MIN_VALUE;
        //最小路径中最大的就是最短完成时间。
        for (int i = 1; i <= map.length; i++) {
            max_ = Math.max(max_, map[K][i]);
        }
        if (max_ == Integer.MAX_VALUE) return -1;
        return max_;
    }
}