题解 | 最小生成树 Prim

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // Prim算法
        int totalCost = 0;
        ArrayList<ArrayList<int[]>> list = new ArrayList(); //list.get(i).get(j)是一个从i出发的边
        for(int i = 0;i<=n;i++){
            list.add(new ArrayList());
        }

        for(int i = 0;i<m;i++){
            //System.out.println(cost[i][0]+" "+cost[i][1]+" "+cost[i][2]);
            list.get(cost[i][0]).add(new int[]{cost[i][1],cost[i][2]});
            list.get(cost[i][1]).add(new int[]{cost[i][0],cost[i][2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);

        boolean[] isVisited = new boolean[n+1];

        pq.add(new int[]{1,0});


        while(!pq.isEmpty()){

            int[] curNode = pq.poll(); 

            int newNode = curNode[0];
            int newCost = curNode[1];
            if(isVisited[newNode]) continue;
            isVisited[newNode] = true;
            totalCost+=newCost;
            //更新堆
            for(int[] edge:list.get(newNode)){
                pq.add(edge);
            }
        }
        return totalCost;
    }
}