在线程"main“java.lang.IllegalArgumentException中的多图异常上的dijkstra :比较方法违反其常规约定

Question

我试图在hackerrank上实现dijkstra，它为每个测试用例中的第一个图都提供了正确的答案，但如果测试用例中有一个以上的图‘`import java.io.*；

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static class Node implements Comparable<Node>{
    int dst=Integer.MAX_VALUE;
    boolean visit=false;
    int index;
    Node(){};
    Node(int index){
        this.index=index;
    };

    public int compareTo(Node n1){
        try{
        return dst<n1.dst?-1:1;
       }catch(Exception e){return 1;}
    }
}
    public static class Edge{
        int index;
        int dst=0;
        Edge(){}
        Edge(int inedx){
            this.index=index;
        }


    }
       public static Node[] dij(ArrayList<Node> nod,ArrayList<LinkedList<Edge>> aee,Node[] nrr){

        while(!nod.isEmpty()){
        Collections.sort(nod);
        Node ne=nod.remove(0);
        LinkedList<Edge> queue=aee.get(ne.index);
        while(!queue.isEmpty()){
            Edge temp=queue.remove(0);
            if((nrr[temp.index].dst>(nrr[ne.index].dst+temp.dst)&&(nrr[ne.index].dst!=Integer.MAX_VALUE))){
                nrr[temp.index].dst=nrr[ne.index].dst+temp.dst;
            }
        }

        }
        return nrr;
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
   Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        while(t-->0){
            int n=in.nextInt();
            Node nrr[]=new Node[n];
            ArrayList<Node> nod=new ArrayList<>();
            for(int i=0;i<n;i++){
                Node ne=new Node(i);
                nrr[i]=ne;
                nod.add(ne);
            }
            int m=in.nextInt();
            ArrayList<LinkedList<Edge>> aee=new ArrayList<LinkedList<Edge>>(n);
            for(int i=0;i<n;i++)
                aee.add(new LinkedList<Edge>());
            for(int i=0;i<m;i++){
                int start=in.nextInt()-1;
                int end=in.nextInt()-1;
                int dst=in.nextInt();
                Edge e1=new Edge(end);
                e1.dst=dst;
                e1.index=end;
                //System.out.println(start+" "+end+" dd "+dst+" "+e1.index);
                aee.get(start).add(e1);
                Edge e2=new Edge(start);
                e2.index=start;
                e2.dst=dst;
               // System.out.println("dd");
                aee.get(end).add(e2);
                nrr[start].visit=true;
                nrr[end].visit=true;
            }
            int k=in.nextInt()-1;
            nrr[k].dst=0;
            Node[] nn=dij(nod,aee,nrr);
            int temp=Integer.MAX_VALUE+0;
      //  System.out.println(temp+" tem");
        for(int i=0;i<n;i++){
            if(i!=k)
                System.out.print(nn[i].dst+" ");
        }
            System.out.println();
        }


    }
}

这是我的队列代码，比较是用来对我的队列进行排序的，这是输入

2
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
78 1231
1 49 8
2 75 36
3 47 38
4 46 11
5 50 61
6 47 45
7 18 38
8 31 39
9 78 18
10 15 11
11 5 1
12 23 26
13 48 58
14 33 60
15 22 3
16 27 27
17 32 17
18 65 40
19 23 55
20 12 41
21 39 37
22 14 18
23 20 25
24 4 19
25 3 12
26 25 15
27 13 6
28 73 10
29 62 60
30 44 18
31 18 44
32 78 3
33 39 29
34 26 42
35 22 24
36 18 36
37 16 41
38 46 54
39 51 2
40 49 16
41 38 22
42 6 44
43 24 49
44 55 36
45 6 63
46 45 10
47 48 41
48 58 21
49 50 24
50 27 17
51 59 38
52 68 33
53 4 4

Your Output
20 25 25 68 86 39 22 70 36 53 91 35 88 27 30 43 54 74 41 
Error
Exception in thread "main" java.util.NoSuchElementException
    at java.util.Scanner.throwFor(Scanner.java:907)
    at java.util.Scanner.next(Scanner.java:1530)
    at java.util.Scanner.nextInt(Scanner.java:2160)
    at java.util.Scanner.nextInt(Scanner.java:2119)
    at Solution.main(Solution.java:67)

我无法改善这一点。

Answer 1

您的compareTo违反了合同。如果两个节点具有相同的dst，则会得到n1.compareTo(n2) == 1和n2.compareTo(n1) == 1。

正确的版本应该如下所示。

 public int compareTo(Node n1){
    return dst<n1.dst?-1:(dst>n1.dst?1:0);
 }

PS:我不知道你为什么要在那里捕捉异常。n1不能为null。