1.题目情况
https://leetcode.cn/problems/connecting-cities-with-minimum-cost/description/
在力扣1135的题目中，考察的问题是最小生成树。在尝试解决的过程中，使用Kruskal算法可以通过全部测试用例。然而，使用我自己编写的Prim的代码时，在64个测试用例中的第56个遇到了答案错误。经过和Kruskal的正确答案比对，发现我写的Prim方法确实有一些边不一样，导致找到的解并非最小。

2.调试的困难
然而，错误用例的n高达50，具体的数组由于长度过长在leetcode中无法完整显示。在大多数简单用例答案正确，特定错误复杂用例无法获得，并且肉眼没有检查出错误的情况下，我优先选择把课程git中的代码根据题目条件稍微改写，得到Prim2方法，具体而言，建图过程和比较器是我额外添加的，但是其逻辑比较简单，没有发现明显错误。而Prim2得到的解和Prim是一致的。也就是说，改写后的Prim2和Prim逻辑可以看成等价。为了进一步定位原因，我把题解中的python代码使用java写了一遍，得到Prim3，而Prim3的答案可以通过所有测试用例。

3.寻找代码差异
的确，Prim3的建模细节和Prim/Prim2有一定的区别。具体的，（1）进pq的对象是目的地和权重，而原来思路是边的两点和权重 （2）不是通过visited数组来判定pq取出的对象是否有效，而是每个城市只会作为目的地被添加一次(通过一个城市集合排除无效点)(虽然没有严谨的证明，但是一个连通分量中如果同一点被作为目的地添加两次，就会成环，这个和!visited[v] || !visited[w]可以理解为等价条件)

4.暂时未能找到错误原因
尽管pq的存储对象和排除无效边的具体实现看起来有所差异，但是在逻辑上，似乎没有找到实际的差异。那么Prim3能够得到正确答案，Prim2的问题具体在哪里？

import java.util.*;

class Solution {
    public int minimumCost(int n, int[][] connections) {
        if (connections.length<n-1){
            return -1;
        }
        return Prim3(n,connections);
    }

    private int Prim3(int n,int[][] connections){
        ArrayList<int[]>[] graph=new ArrayList[n];
        for (int i=0;i<n;i++){
            graph[i]=new ArrayList<>();
        }
        for (int[] info:connections){
            int a=info[0]-1,b=info[1]-1,cost=info[2];
            graph[a].add(new int[]{b,cost});
            graph[b].add(new int[]{a,cost});
        }
        PriorityQueue<int[]> out_edges=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        out_edges.add(new int[]{0,0});
        HashSet<Integer> intree=new HashSet<>();
        int ans=0;
        while (!out_edges.isEmpty() && intree.size()!=n){
            int[] cur=out_edges.poll();
            int cost=cur[0],city=cur[1];
            if (intree.add(city)){
                ans+=cost;
                for (int[] newInfo:graph[city]){
                    out_edges.add(new int[]{newInfo[1],newInfo[0]});
                }
            }
        }
        return intree.size()==n?ans:-1;
    }

    public int Prim2(int n,int[][] connections){

        HashMap<Integer,Integer>[] graph=new HashMap[n];
        for (int i=0;i<n;i++){
            graph[i]=new HashMap<>();
        }
        for (int[] info:connections){
            int v=info[0]-1,w=info[1]-1,weight=info[2];
            graph[v].put(w,weight);
            graph[w].put(v,weight);
        }
        PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });
        boolean visited[] = new boolean[n];
        visited[0] = true;
        for(int w: graph[0].keySet())
            pq.add(new int[] {0, w, graph[0].get(w)});

        int res=0;
        int cnt=0;
        while(!pq.isEmpty() && cnt<n-1){
            int[] minEdge=pq.poll();
            if(visited[minEdge[0]] && visited[minEdge[1]])
                continue;
            res+=minEdge[2];
            cnt++;
            int newv = visited[minEdge[0]] ? minEdge[1] : minEdge[0];
            visited[newv] = true;
            for(int w: graph[newv].keySet())
                if(!visited[w])
                    pq.add(new int[] {newv,w,graph[newv].get(w)});
        }
        return cnt==n-1?res:-1;
    }
}