Одному таксисту приснился красочный сон. Во сне он живет и работает в некотором городе, где абсолютно все улицы с односторонним движением. Эти улицы устроены так, что невозможно…

Для решения этой задачи нам необходимо найти максимальные расстояния от заданного перекрестка \( S \) до всех остальных перекрестков в направленной графовой сети. Так как в данной сети нет циклов, мы можем использовать алгоритм поиска в глубину (DFS) или алгоритм Дейкстры. Однако, учитывая, что мы ищем максимальные дистанции, вместо минимальных, можно немного адаптировать алгоритм Дейкстры.

Шаги решения

1. Представление графа: Мы можем использовать список смежности, чтобы хранить наши улицы и их длины. Каждый перекресток будет иметь список улиц, выходящих из него.

2. Алгоритм Дейкстры: Поскольку граф является ациклическим, алгоритм Дейкстры будет находить максимальные пути, если мы будем хранить максимальные расстояния и обновлять их при нахождении более длинного пути.

3. Инициализация: Мы инициализируем массив max_distance длины \( n \) (количество перекрестков) со значением \(-\infty\) для всех перекрестков, кроме стартового \( S \), где max_distance[S] = 0. Также нам потребуется очередь для обработки перекрестков.

4. Обработка очереди: Обрабатываем перекрестки из очереди и обновляем максимальные расстояния для всех смежных перекрестков. Если находим больший путь, обновляем значение и добавляем в очередь для дальнейшей обработки.

5. Вывод результата: После завершения алгоритма мы просто выводим max_distance для каждого перекрестка. Если значение все еще остается \(-\infty\), это означает, что невозможно добраться до этого перекрестка из \( S \), и мы выводим -.

Примерный код на Python:

import sys
import heapq

def max_distance_from_source(n, m, edges, S):
    graph = [[] for _ in range(n + 1)]

    for a, b, d in edges:
        graph[a].append((b, d))

    # Инициализируем дистанции
    max_distance = [-float('inf')] * (n + 1)
    max_distance[S] = 0

    # Используем очередь для обработки
    queue = [(0, S)]  # (расстояние, перекресток)

    while queue:
        current_distance, current_node = heapq.heappop(queue)
        current_distance = -current_distance  # Преобразуем обратно для максимальных расстояний

        # Проходим по всем соседним узлам
        for neighbor, distance in graph[current_node]:
            if current_distance + distance > max_distance[neighbor]:
                max_distance[neighbor] = current_distance + distance
                heapq.heappush(queue, (-max_distance[neighbor], neighbor))

    # Формируем результат
    result = []
    for i in range(1, n + 1):
        if max_distance[i] == -float('inf'):
            result.append('-')
        else:
            result.append(str(max_distance[i]))
            
    return result

# Ввод данных
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
S = int(input().strip())

# Получаем результат
result = max_distance_from_source(n, m, edges, S)

# Выводим результат
print('\n'.join(result))

Объяснение кода:

• Мы создаем граф в виде списка смежности.
• Используем максимум для корректного обновления расстояний.
• Алгоритм работает достаточно эффективно для ограничений задачи и позволяет находить максимальные расстояния как требуется.

Таким образом, используя вышеприведенные шаги, мы можем найти максимальную стоимость всех маршрутов такси из стартового перекрестка \( S \) до всех остальных перекрестков.