Нелинейные структуры данных С++

Купцы одного сказочного мира учредили свой ежегодный съезд – Континентальный Купеческий Конгресс, где обсуждают свои проблемы. Каждая страна отправляет на съезд по одному делегату, а расходы на пересечение границ (визы) оплачиваются из общей кассы. Посчитайте эти расходы (1 пиастр за каждое пересечение), если известна страна проведения конгресса, а купцы следуют на съезд маршрутами, на которых количество пересечений границ минимально.

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