Minimum Time to Visit Disappearing Nodes

This approach uses a basic implementation of Dijkstra's algorithm. It finds the shortest path from the source node 0 to all other nodes. The main characteristic of this naive version is how it selects the next node to process. At each step, it performs a linear scan across all nodes to find the unvisited one with the minimum current travel time. The core logic is adapted to handle the disappearance constraint: a path to a node is only considered if the arrival time is strictly less than the node's disappearance time. While correct, this method is inefficient due to the repeated linear scans.

• Graph Representation: Build an adjacency list from the edges array. adj[i] will store a list of pairs, where each pair consists of a neighbor node and the edge weight (time).
• Initialization: Create a minTime array of size n initialized to infinity, representing the shortest time from node 0. Set minTime[0] = 0. Also, create a boolean visited array of the same size, initialized to false.
• Iterative Search: Loop n times. In each iteration:
  • Find the unvisited node u with the smallest minTime value. This requires a linear scan through all n nodes.
  • If no such node is found (all remaining unvisited nodes have infinite time), it means they are unreachable, so break the loop.
  • Mark node u as visited.
• Edge Relaxation: For each neighbor v of the selected node u:
  • Calculate the time to reach v through u: newTime = minTime[u] + weight(u, v).
  • Constraint Check: This new path is only considered if it's a valid visit (newTime < disappear[v]) and it's a shorter path (newTime < minTime[v]).
  • If both conditions are met, update minTime[v] = newTime.
• Finalization: After the loops complete, iterate through the minTime array. Any value that is still infinity means the corresponding node is unreachable. Replace these values with -1.

The algorithm begins by converting the edge list into a more usable adjacency list format. It then initializes a minTime array to keep track of the shortest time to reach each node, with minTime[0] set to 0 and all others to a value representing infinity. The main part of the algorithm is a loop that runs up to n times. In each iteration, it searches for the unvisited node u that is currently closest to the source. Once u is found, it is marked as visited, and we try to "relax" its edges. For each neighbor v of u, we calculate the time it would take to reach v by passing through u. If this new time is less than disappear[v] and also less than the current minTime[v], we update minTime[v]. This process continues until all reachable nodes have been visited. Finally, any node with an infinite minTime is marked as unreachable (-1).

import java.util.*;

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }

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

        boolean[] visited = new boolean[n];

        for (int count = 0; count < n; count++) {
            int u = -1;
            int t = Integer.MAX_VALUE;

            // Find the unvisited node with the smallest time
            for (int i = 0; i < n; i++) {
                if (!visited[i] && minTime[i] < t) {
                    t = minTime[i];
                    u = i;
                }
            }

            if (u == -1) {
                break; // All remaining nodes are unreachable
            }

            visited[u] = true;

            for (int[] edge : adj.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                
                int newTime = t + weight;
                if (newTime < disappear[v] && newTime < minTime[v]) {
                    minTime[v] = newTime;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (minTime[i] == Integer.MAX_VALUE) {
                minTime[i] = -1;
            }
        }
        return minTime;
    }
}