_1334.java

packagecom.fishercoder.solutions.secondthousand;

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

publicclass_1334 {
publicstaticclassSolution1 {
/*
 * Dijkstra's algorithm to find the shortest path from each node to all possibly reachable nodes within limit.
 * Dijkstra's algorithm applies to weights are non-negative problems.
 * Keys to implement Dijkstra's algorithm:
 * 1. use an array to hold the shortest distance to each node for each node;
 * 2. initially, only the starting node distance is zero, all other nodes' distances to be infinity;
 * 3. use a PriorityQueue to poll out the next node that has the shortest distance and scan through all its neighbors,
 * if the cost can be updated, then put it into the priority queue (this is a critical key to implement Dijkstra!)
 * Only when this node's code could be updated/shortened, we'll put it into the priority queue/minHeap,
 * so that next time, it'll be polled and processed based on priority order
 */
publicintfindTheCity(intn, int[][] edges, intdistanceThreshold) {
List<List<int[]>> graph = newArrayList();
int[][] shortestPaths = newint[n][n];
for (inti = 0; i < n; i++) {
graph.add(newArrayList<>());
 }
for (int[] edge : edges) {
intsource = edge[0];
intdest = edge[1];
intweight = edge[2];
graph.get(source).add(newint[] {dest, weight});
graph.get(dest).add(newint[] {source, weight});
 }
for (inti = 0; i < n; i++) {
dijkstraAlgo(graph, i, shortestPaths[i]);
 }
returnfindCityWithFewestReachableCities(shortestPaths, distanceThreshold);
 }

privateintfindCityWithFewestReachableCities(
int[][] shortestPaths, intdistanceThreshold) {
intans = 0;
intfewestReachable = shortestPaths.length;
for (inti = 0; i < shortestPaths.length; i++) {
intreachable = 0;
for (intj = 0; j < shortestPaths[0].length; j++) {
if (i != j && shortestPaths[i][j] <= distanceThreshold) {
reachable++;
 }
 }
if (reachable <= fewestReachable) {
fewestReachable = reachable;
ans = i;
 }
 }
returnans;
 }

privatevoiddijkstraAlgo(List<List<int[]>> graph, intstartCity, int[] shortestPath) {
Arrays.fill(shortestPath, Integer.MAX_VALUE);
shortestPath[startCity] = 0;
PriorityQueue<int[]> minHeap = newPriorityQueue<>((a, b) -> a[1] - b[1]);
minHeap.offer(newint[] {startCity, 0});
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
intcurrCity = curr[0];
intcurrCost = curr[1];
if (currCost > shortestPath[currCity]) {
continue;
 }
for (int[] neighbor : graph.get(currCity)) {
intneighborCity = neighbor[0];
intneighborCost = neighbor[1];
if (currCost + neighborCost < shortestPath[neighborCity]) {
shortestPath[neighborCity] = currCost + neighborCost;
minHeap.offer(newint[] {neighborCity, shortestPath[neighborCity]});
 }
 }
 }
 }
 }
}