Kattis Cross Country题Java实现运行时错误排查求助

我尝试用Java实现Dijkstra算法解决Kattis平台的《Cross Country》问题，但在第二个测试用例后出现运行时错误。我自行排查过输入输出格式、边界限制，算法逻辑看似正确，还请教过他人，但错误仍未消除。

猜测的错误原因 #

• 可能存在输入输出格式错误
• 可能未正确遵守边界限制（我已检查，但可能有遗漏）
• 算法逻辑似乎正确

我的代码 #

challenge.java #

package graph;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;


public class challenge {

    // Zwei Wochen Ski Trip
    // Charles hat Schoki vergessen und musste home gehen um sie zu holen
    // Alle Parkplätze in der Nähe des Treffpunktes besetzt
    // Workout-Tagebuch von Charles ist gegeben -> Schnellsten Weg zum Treffpunkt finden
    // intersection = Schnittpunkt
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // Anzahl Schnittpunkte
        int S = scanner.nextInt(); // Index des Schnittpunktes wo Charles sein Auto geparkt hat
        int T = scanner.nextInt(); // Index des Schnittpunktes wo Treffpunkt

        ausschlusskriterien(N,S,T);

        Graph graph = new Graph(N);

        createGraph(scanner, N, graph);

        // Berechne den kürzesten Weg
        int shortestPath = dijkstra(N, S, T, graph);
        System.out.println(shortestPath);

        scanner.close();

    }

    private static void ausschlusskriterien(int N, int S, int T) {
        if (N < 1 || N > 1000) {
            throw new IllegalArgumentException("Ungültige Anzahl von Schnittpunkten (N). Muss zwischen 1 und 1000 liegen.");
        }
        if (S < 0 || S >= N) {
            throw new IllegalArgumentException("Ungültiger Start-Schnittpunkt (S). Muss zwischen 0 und N-1 liegen.");
        }
        if (T < 0 || T >= N) {
            throw new IllegalArgumentException("Ungültiger Ziel-Schnittpunkt (T). Muss zwischen 0 und N-1 liegen.");
        }
    }


    private static int dijkstra(int N, int S, int T, Graph graph) {
        int[] dist = new int[N]; // Array zur Speicherung der Distanzen
        boolean[] visited = new boolean[N]; // Array zur Markierung der besuchten Knoten

        // Initialisiere alle Distanzen als unendlich, außer dem Startknoten S als 0
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        // Suche den kürzesten Pfad mit Dijkstra's Algorithmus
        for (int i = 0; i < N - 1; i++) {
            int u = findMinDistance(dist, visited); // Wähle den Knoten mit der geringsten Distanz aus

            visited[u] = true; // Markiere den Knoten als besucht

            // Aktualisiere die Distanzen der benachbarten Knoten, falls ein kürzerer Pfad gefunden wurde
            List<Graph.Edge> neighbors = graph.getNeighbors(u);
            for (Graph.Edge edge : neighbors) {
                int v = edge.getDestination();
                int weight = edge.getWeight();
                if (!visited[v] && dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        return dist[T];
    }


    private static int findMinDistance(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }

        if (minIndex == -1) {
            throw new RuntimeException("Kein unbesuchter Knoten mit geringerer Distanz gefunden");
        }

        return minIndex;
    }

    private static void createGraph(Scanner scanner, int N, Graph graph) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int weight = scanner.nextInt();
                if (i != j) {
                    if (weight < 1 || weight >= 10000) {
                        throw new IllegalArgumentException("Ungültiges Gewicht (D(i,j)). Muss zwischen 1 und 9999 liegen.");
                    }
                    graph.addEdge(i, j, weight);
                }
            }
        }
    }

}

Graph.java #

package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class Graph {
    private int numNodes;
    private Map<Integer, List<Edge>> adjacencyList;

    public Graph(int numNodes) {
        this.numNodes = numNodes;
        adjacencyList = new HashMap<>();
        for(int i = 0; i < numNodes; i++){
            adjacencyList.put(i, new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination, int weight){
        Edge edge = new Edge(destination, weight);
        adjacencyList.get(source).add(edge);
    }

    public List<Edge> getNeighbors(int node) {
        return adjacencyList.get(node);
    }

    public int getNumNodes() {
        return numNodes;
    }

    static class Edge {
        private int destination;
        private int weight;

        public Edge(int destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }

        public int getDestination() {
            return destination;
        }

        public int getWeight() {
            return weight;
        }
    }
}

非常感谢，祝周末愉快！

内容的提问来源于stack exchange，提问作者Maximilian