Тестовый пример HackerRank не удался. Дейкстра Shortest Reach 2 [закрыто] ⇐ JAVA

[Anonymous]

Я застрял на тестовом примере 7, который оказался единственным, который не удался. Я пробовал несколько раз, но проблема одна и та же.
Формат ввода: первая строка содержит количество тестовых примеров.
Каждый тестовый пример следующим образом:
Первая строка содержит два целых числа, разделенных пробелами, и — количество узлов и ребер в графе.
Каждая из следующих строк строк содержит три целых числа, разделенных пробелами, а также начальный и конечный узлы ребра, а также длину ребра.
Последняя строка каждого тестового примера имеет целое число, обозначающее начальную точку. позиция.
вопрос о хакерском ранге
Вот тестовый пример
Ожидаемый результатВот полный Java-код, который я пробовал (который прошел все тестовые примеры, кроме тестового примера 7) —
import java.io.*;
import java.util.*;
import java.util.stream.*;

class Result {

public static class Pair implements Comparable
{
int node;
int dist;

public Pair(int node, int dist) {
this.node = node;
this.dist = dist;
}

@Override
public int compareTo(Pair other) {
return Integer.compare(this.dist, other.dist);
}
}

public static List shortestReach(int n, List edges, int s) {
List adjList = new ArrayList(n);
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList());
}

for (List edge : edges) {
int src = edge.get(0) - 1;
int dest = edge.get(1) - 1;
int weight = edge.get(2);
adjList.get(src).add(new Pair(dest, weight));
adjList.get(dest).add(new Pair(src, weight));
}

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist = 0;

PriorityQueue pq = new PriorityQueue();
pq.add(new Pair(s - 1, 0));

while (!pq.isEmpty()) {
Pair curr = pq.poll();
int u = curr.node;

if (curr.dist > dist) {
continue;
}

for (Pair neighbor : adjList.get(u)) {
int v = neighbor.node;
int weight = neighbor.dist;

if (dist + weight < dist[v]) {
dist[v] = dist + weight;
pq.add(new Pair(v, dist[v]));
}
}
}

List result = new ArrayList();
for (int i = 0; i < n; i++) {
if (i == s - 1) continue;
result.add(dist == Integer.MAX_VALUE ? -1 : dist);
}

return result;
}

}

public class Solution {

public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = Integer.parseInt(bufferedReader.readLine().trim());

for (int tItr = 0; tItr < t; tItr++) {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);

List edges = new ArrayList();

for (int i = 0; i < m; i++) {
edges.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(Collectors.toList())
);
}

int s = Integer.parseInt(bufferedReader.readLine().trim());

List result = Result.shortestReach(n, edges, s);

bufferedWriter.write(result.stream().map(Object::toString).collect(Collectors.joining(" "))+ "\n");
}

bufferedReader.close();
bufferedWriter.close();
}
}


Вот ошибка:
Time limit exceeded Your code did not execute within the time limits. Please optimize your code. For more information on execution time limits, refer to the environment page.

The environment page doesn't exist.


Подробнее здесь: https://stackoverflow.com/questions/785 ... st-reach-2