Олимпиада по алхимии (решение через графы) кратко

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

Московская олимпиада VIII. Заочный тур 2005—2006 учебного года.

Задание

В государстве алхимиков есть N населенных пунктов, пронумерованных числами от 1 до N, и М дорог. Населенные пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населенных пункта, и для проезда по ней требуется T_j минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному гонцу на город) с информацией про олимпиаду.

Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберется до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.

Ввод

Во входном файле сначала записаны 3 числа: N, M, К — количество населенных пунктов, количество дорог и количество городов (2 <= N <= 1000, 1 <= М <= 10000, 1 <= К <= M). Далее записан номер столицы С (1 <= С <= M). Следующие К чисел задают номера городов. Далее следуют М троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Тi, — время для проезда по ней (1 <= Ti <= 100).

Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).

Вывод

Выведите в выходной файл K пар чисел: для каждого города должен быть выведен его номер и минимальное время, спустя которое гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Об этом говорит сайт https://intellect.icu . Пары в выходном файле должны быть упорядочены по времени прибытия гонца.

Пример ввода         Пример вывода
5 4 5 1	             1 0	
12 3 4 5             2 1	
1 2 1	             3 11	
2 3 10	             4 111	
3 4 100	             5 211	
4 5 100		


5 5 3 1	             5 1	
2 4 5	             2 1	
2 1 1	             4 101	
2 3 10		
3 4 100		
4 5 100		
1 5 1		

Решение

Примем населенные пункты за вершины графа, а дороги между ними - за взвешенные ребра. Формально нам надо найти кратчайшие пути от заданной вершины графа (столицы) до всех остальных вершин.

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

Формальное описание

Olymp()
1. Считать из файла список ребер графа и их вес.
2. Создать матрицу смежности для графа.
3. По алгоритмы Дейкстры найти наикратчайшие расстояния от вершины-
   столицы до всех остальных вершин графа(выполнить пп. 3.1-3.4):
   3.1. Инициализировать расстояния до вершин бесконечностью, 
        все метки о нахождении кратчайшего пути нулями.
   3.2. Установить расстояние до стартовой вершины равное 0.
   3.3. Пока не найдены кратчайшие пути для всех вершин, повторять 
        пп. 3.3.1-3.3.3:
        3.3.1. Найти вершину, кратчайший путь для которой не найден,
               с минимальным расстоянием.
        3.3.2. Считать, что кратчайший путь для данной вершины найден.
        3.3.3. Обновить расстояния до инцидентных к текущей вершин.
4. Отсортировать вершины по возрастанию расстояния до них.
5. Выбрать первую вершину.
6. Пока не обработаны все вершины, повторять пп. 6.1.-6.2:
   6.1. Если текущая вершина является городом, то вывести ее номер
        и расстояние о нее.
   6.2. Перейти к следующей вершине графа.

Граф задачи для первого теста. (Зеленый фон имеют вершины-города, красную границу - столица, в скобках указаны минимальные расстояния до вершины)

Граф задачи для второго теста. (Зеленый фон имеют вершины-города, красную границу - столица, в скобках указаны минимальные расстояния до вершины)

На этом все! Теперь вы знаете все про олимпиада по алхимии решение через графы , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое олимпиада по алхимии решение через графы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов