Ориентированный граф, время передачи по ребру t > 0 (произвольное положительное). Сигнал стартует из вершины 0. Найти время достижения каждой вершины алгоритмом Дейкстры.
Идея. Поддерживаем множество S вершин с финальным расстоянием. На каждом шаге берём вершину с минимальной текущей оценкой dist вне S, фиксируем её, релаксируем соседей. Неотрицательность весов гарантирует, что зафиксированное расстояние уже не улучшится.