Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

👨‍💻 Алгоритм:

1⃣Представьте граф в виде списка смежности.

2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

function networkDelayTime($times, $n, $k) {
    $graph = [];
    for ($i = 1; $i <= $n; $i++) {
        $graph[$i] = [];
    }
    foreach ($times as $time) {
        $graph[$time[0]][] = [$time[1], $time[2]];
    }

    $minHeap = new SplPriorityQueue();
    $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $minHeap->insert([$k, 0], 0);
    $minTime = array_fill(1, $n, INF);
    $minTime[$k] = 0;

    while (!$minHeap->isEmpty()) {
        $data = $minHeap->extract();
        $time = $data['priority'];
        $node = $data['data'][0];
        foreach ($graph[$node] as $neighbor) {
            $newTime = $time + $neighbor[1];
            if ($newTime < $minTime[$neighbor[0]]) {
                $minTime[$neighbor[0]] = $newTime;
                $minHeap->insert([$neighbor[0], $newTime], -$newTime);
            }
        }
    }

    $maxTime = max($minTime);
    return $maxTime == INF ? -1 : $maxTime;
}

Ставь 👍 и забирай 📚 Базу знаний