无向图最短路径问题升级版

import java.util.*;

public class NoPointerChartWithMoney {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int money = sc.nextInt();
        int E = sc.nextInt();
        Set<Integer> unVisited = new HashSet<>(N);  //记录未访问节点
        Set<Integer> visitied = new HashSet<>(N); //记录已经访问的节点
        int[] M = new int[N];  //记录每个节点的过路费
        int[][] V = new int[N][N];  //记录每条边的权重，初始值为0代表没有边
        int[][] MIN = new int[N][money+1];  //记录从第一个节点到第i个节点还剩j元时的最短路径
        List<Integer>[][] MIN_line = new List[N][money+1];
        for(int i=0;i<N;i++){
            for(int j=0;j<money+1;j++){
                MIN[i][j]=999;
            }
        }
        MIN[0][money]=0;
        MIN_line[0][money] = new ArrayList<>();
        MIN_line[0][money].add(0);
        for(int i=0;i<N;i++){
            M[i]=sc.nextInt();
        }
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                V[i][j]=Integer.MAX_VALUE;
            }
        }
        for(int i=0;i<E;i++){
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int v = sc.nextInt();
            V[v1][v2] = v;
            V[v2][v1] = v;
        }
        for(int i=1;i<N;i++){
            unVisited.add(i);
        }
        visitied.add(0);

        int choice = 0;  //中间节点下标，每次选出当前结点到所有可达未标记结点的最短路径端点为中间结点下标
        while (unVisited.size() > 0) {   //当仍然有未标记结点的时候
            int tempMin = Integer.MAX_VALUE;  //记录从中间节点到所有可达结点中的最小值（最短路径）
            int tempMinI = -1;  //记录最短路径的端点下标
            Iterator<Integer> iti = unVisited.iterator();
            while (iti.hasNext()) {  //对于所有未标记的结点
                int i = iti.next();
                if (V[choice][i] != Integer.MAX_VALUE) {   //如果中间结点到此未标记结点有边
                    for(int j=0;j<=money;j++) {
                        if(MIN[choice][j]!=999&&j-M[i]>0) {
                            if (MIN[i][j-M[i]] > V[choice][i] + MIN[choice][j]) {   //计算中间结点到当前结点的最短路径
                                MIN[i][j - M[i]] = V[choice][i] + MIN[choice][j];
                                MIN_line[i][j-M[i]] = new ArrayList<>(MIN_line[choice][j]);
                                MIN_line[i][j-M[i]].add(i);
                            }

                            if (MIN[i][j-M[i]]  < tempMin) {   //计算当前结点到所有可达未标记结点的最短路径
                                tempMin = MIN[choice][j];
                                tempMinI = i;
                            }
                        }
                    }

                }
            }
            unVisited.remove(tempMinI);visitied.add(tempMinI);  //将当前结点记录未已经标记
            choice = tempMinI; //重新定位中间结点
        }


//        5 100 6
//        11 20 5 32 18
//        0 2 1
//        0 3 2
//        3 4 6
//        1 2 4
//        1 3 5
//        1 4 3


        //打印最终的MIN数组
        for(int j=0;j<money+1;j++){
            System.out.print(j+"\t");
        }
        System.out.println();
        for(int i=0;i<N;i++){
            for(int j=0;j<money+1;j++){
                if(MIN[i][j]!=999)
                    System.out.print(MIN[i][j]+"\t");
                else
                    System.out.print(" "+"\t");
            }
            System.out.println();
        }

        int tempMin = 999;
        int tempMinj = 0;
        for(int j=0;j<=money;j++){
            if(MIN[N-1][j]!=999){
                if(MIN[N-1][j]<=tempMin) {  //这里用小于等于会自动挑选剩余钱数最多的最短路径
                    tempMin = MIN[N - 1][j];
                    tempMinj = j;
                }
            }
        }

        System.out.println(tempMin+" "+tempMinj);  //打印最短路径长度和剩余的钱数
        Iterator<Integer> it = MIN_line[N-1][tempMinj].iterator();   //打印最短路径
        System.out.print(it.next());
        while (it.hasNext()){
            System.out.print("->"+it.next());
        }
        System.out.println();
    }
}