_3241.java

packagecom.fishercoder.solutions.fourththousand;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.List;
importjava.util.PriorityQueue;

publicclass_3241 {
publicstaticclassSolution1 {
/*
 * This is my original solution during the contest, it's correct but not efficient enough, so got TLE on LeetCode.
 * TODO: figure out a more efficient approach.
 */
publicint[] timeTaken(int[][] edges) {
int[] times = newint[edges.length + 1];
List<Integer>[] graph = newArrayList[edges.length + 1];
for (inti = 0; i < edges.length + 1; i++) {
graph[i] = newArrayList<>();
 }
for (int[] edge : edges) {
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
 }
for (inti = 0; i < edges.length + 1; i++) {
times[i] = markAllNodes(graph, i);
 }
returntimes;
 }

privateintmarkAllNodes(List<Integer>[] graph, intstartNode) {
PriorityQueue<int[]> q = newPriorityQueue<>((a, b) -> a[1] - b[1]);
q.offer(newint[] {startNode, 0});
int[] shortestTime = newint[graph.length];
Arrays.fill(shortestTime, Integer.MAX_VALUE);
shortestTime[startNode] = 0;
intmaxTime = -1;
while (!q.isEmpty()) {
int[] curr = q.poll();
intcurrNode = curr[0];
intcurrTime = curr[1];
if (currTime > shortestTime[currNode]) {
continue;
 }
maxTime = shortestTime[currNode];
for (intneighbor : graph[currNode]) {
if (neighbor % 2 == 0) {
if (currTime + 2 < shortestTime[neighbor]) {
shortestTime[neighbor] = currTime + 2;
maxTime = Math.max(maxTime, shortestTime[neighbor]);
q.offer(newint[] {neighbor, shortestTime[neighbor]});
 }
 } else {
if (currTime + 1 < shortestTime[neighbor]) {
shortestTime[neighbor] = currTime + 1;
maxTime = Math.max(maxTime, shortestTime[neighbor]);
q.offer(newint[] {neighbor, shortestTime[neighbor]});
 }
 }
 }
 }
returnmaxTime;
 }
 }
}