_3112.java

packagecom.fishercoder.solutions.fourththousand;

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

publicclass_3112 {
publicstaticclassSolution1 {
/*
 * My completely original solution: Dijkstra's algorithm!
 */
publicint[] minimumTime(intn, int[][] edges, int[] disappear) {
List<int[]>[] graph = newArrayList[n];
for (inti = 0; i < n; i++) {
graph[i] = newArrayList<>();
 }
for (int[] edge : edges) {
graph[edge[0]].add(newint[] {edge[1], edge[2]});
graph[edge[1]].add(newint[] {edge[0], edge[2]});
 }
int[] ans = newint[n];
int[] shortestTimes = newint[disappear.length];
Arrays.fill(shortestTimes, Integer.MAX_VALUE);
shortestTimes[0] = 0;
dijkstra(graph, disappear, shortestTimes);
for (inttarget = 1; target < n; target++) {
if (shortestTimes[target] == Integer.MAX_VALUE
 || shortestTimes[target] >= disappear[target]) {
ans[target] = -1;
 } else {
ans[target] = shortestTimes[target];
 }
 }
returnans;
 }

privatevoiddijkstra(List<int[]>[] graph, int[] disappear, int[] shortestTimes) {
PriorityQueue<int[]> q = newPriorityQueue<>((a, b) -> a[1] - b[1]);
q.offer(newint[] {0, 0});
while (!q.isEmpty()) {
int[] curr = q.poll();
intcurrNode = curr[0];
intcurrCost = curr[1];
if (currCost > shortestTimes[currNode]) {
continue;
 }
for (int[] neighbor : graph[currNode]) {
intneighborNode = neighbor[0];
intneighborCost = neighbor[1];
if (neighborCost + currCost < shortestTimes[neighborNode]
 && neighborCost + currCost < disappear[neighborNode]) {
shortestTimes[neighborNode] = neighborCost + currCost;
q.offer(newint[] {neighborNode, shortestTimes[neighborNode]});
 }
 }
 }
 }
 }
}