Задача С. Дед Максим собирается отправиться в путешествие по Флатландии, но у него есть только мопед с ограниченной

города с номерами \(a_i\) и \(b_i\) и имеет длину \(c_i\) километров. Дед Максим хочет найти кратчайший путь от города с номером 1 до города с номером \(п\) такой, чтобы минимизировать количество дозаправок.

Для решения данной задачи можно использовать алгоритм Дейкстры. Алгоритм Дейкстры позволяет найти кратчайший путь от одной вершины графа до всех остальных вершин. В нашем случае, вершинами графа будут города, и ребрами графа - дороги между городами.

Шаги алгоритма Дейкстры:
1. Создаем массив расстояний dist, в котором будем хранить текущие расстояния от вершины 1 до всех остальных вершин. Изначально все расстояния, кроме расстояния из вершины 1 в вершину 1, равны бесконечности.
2. Создаем массив посещенных вершин visited, в котором будем хранить информацию о том, посещали мы данную вершину или нет. Изначально все вершины непосещены.
3. Инициализируем расстояние от вершины 1 до вершины 1 равным 0.
4. Пока есть непосещенные вершины:
4.1. Ищем вершину u с минимальным расстоянием dist[u], среди непосещенных вершин.
4.2. Помечаем вершину u как посещенную.
4.3. Для каждой вершины v, смежной с вершиной u:
4.3.1. Если dist[v] > dist[u] + c, где c - длина ребра (дороги) между вершинами u и v, то обновляем расстояние dist[v] = dist[u] + c.

После выполнения алгоритма Дейкстры, dist[п] будет содержать расстояние от вершины 1 до города с номером п. Таким образом, минимальное количество дозаправок будет равно dist[п] / 3 (с округлением вверх).

Например, пусть п = 5, т = 7 и заданы следующие дороги: (1, 2, 1), (1, 3, 2), (2, 4, 3), (3, 4, 2), (3, 5, 1), (4, 5, 3), (5, 1, 1). Перейдем к решению:

1. Создаем массив dist, инициализируем все элементы, кроме dist[1], значением бесконечность.
2. Создаем массив visited, все элементы инициализируем значением False.
3. Инициализируем dist[1] = 0.
4. Начинаем выполнение алгоритма Дейкстры:
4.1. Выбираем вершину 1 как текущую.
4.2. Обновляем значения dist для смежных вершин:
- dist[2] = min(dist[2], dist[1] + 1) = min(∞, 0 + 1) = 1
- dist[3] = min(dist[3], dist[1] + 2) = min(∞, 0 + 2) = 2
4.3. Помечаем вершину 1 как посещенную.
4.4. Выбираем вершину с минимальным значением dist среди непосещенных вершин. Это вершина 2 (dist[2] = 1).
4.5. Обновляем значения dist для смежных вершин:
- dist[4] = min(dist[4], dist[2] + 3) = min(∞, 1 + 3) = 4
4.6. Помечаем вершину 2 как посещенную.
4.7. Выбираем вершину с минимальным значением dist среди непосещенных вершин. Это вершина 3 (dist[3] = 2).
4.8. Обновляем значения dist для смежных вершин:
- dist[4] = min(dist[4], dist[3] + 2) = min(4, 2 + 2) = 4
- dist[5] = min(dist[5], dist[3] + 1) = min(∞, 2 + 1) = 3
4.9. Помечаем вершину 3 как посещенную.
4.10. Выбираем вершину с минимальным значением dist среди непосещенных вершин. Это вершина 5 (dist[5] = 3).
4.11. Обновляем значения dist для смежных вершин:
- dist[1] = min(dist[1], dist[5] + 1) = min(∞, 3 + 1) = 4
4.12. Помечаем вершину 5 как посещенную.
4.13. Все вершины посещены, алгоритм заканчивает работу.

После выполнения алгоритма Дейкстры, dist = [0, 1, 2, 4, 3]. Таким образом, минимальное количество дозаправок для пути от города 1 до города 5 равно 3 / 3 = 1.

Очевидно, что алгоритм Дейкстры применим для решения задачи С, так как задача С может быть представлена в виде графа, где вершинами будут города, а ребрами - дороги. Применение данного алгоритма позволит найти кратчайший путь с минимальным количеством дозаправок.