Code Logo

Campus Announcement Delay with Dijkstra

Published at22 Apr 2026
Created by
Dijkstra Easy 0 views
Like0

A campus announcement system sends a message from one control room to several buildings. Each directed connection is written as [from, to, time], meaning the message can travel in that direction and takes that many minutes.

You are given the list of transmission links, the total number of buildings n, and the starting building. Return how long it takes until every building receives the message.

If some building can never be reached from the start, return -1. Otherwise, return the largest shortest-path time among all buildings, because that last building determines when the full campus has received the announcement.

This is an easy Dijkstra variation: instead of asking for one destination, you compute the shortest time to every node and then take the maximum of those values.

Example Input & Output

Example 1
Input
times = [[1,2,1], [1,3,4], [2,3,2], [3,4,1]], n = 4, start = 1
Output
4
Explanation

The last building receives the message after 4 minutes.

Example 2
Input
times = [], n = 1, start = 1
Output
0
Explanation

A single building already has the announcement at time zero.

Example 3
Input
times = [[1,2,1]], n = 3, start = 1
Output
-1
Explanation

Building 3 cannot be reached, so the full network never receives the message.

Algorithm Flow

Recommendation Algorithm Flow for Campus Announcement Delay with Dijkstra
Recommendation Algorithm Flow for Campus Announcement Delay with Dijkstra

Solution Approach

The main algorithm is still Dijkstra's algorithm. The difference is what you do after the shortest distances have been computed.

Build a directed adjacency list from the transmission links. Then run Dijkstra from the starting building to fill a distance array. Each entry tells you the earliest known time for the message to reach that building.

After the priority queue finishes, scan the distance array. If any building still has an infinite distance, then it was unreachable and the correct answer is -1. Otherwise, the answer is the largest value in the array, because that building receives the message last.

This works well because Dijkstra gives the shortest transmission time to every reachable node in a weighted directed graph. Once you have those values, the delay for the whole network is just the maximum shortest-path distance.

The runtime remains O((n + m) log n), which is the standard cost for this algorithm with a heap-based priority queue.

Best Answers

java
import java.util.*;

class Solution {
    public int campus_announcement_delay_with_dijkstra(int[][] times, int n, int start) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

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

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int cost = current[0];
            int node = current[1];
            if (cost > dist[node]) {
                continue;
            }
            for (int[] edge : graph.get(node)) {
                int next = edge[0];
                int candidate = cost + edge[1];
                if (candidate < dist[next]) {
                    dist[next] = candidate;
                    pq.offer(new int[]{candidate, next});
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            answer = Math.max(answer, dist[i]);
        }
        return answer;
    }
}