Задачи (2018/2019)

Задача 9а. [5.4.2, стр. 272] dijkstra.c
Даден е ориентиран граф с положителни тегла (дължини) на дъгите. Да се намери минимален път от зададен връх до всички други върхове на графа.

Вход:
На стандартниявхода се задава най-напред броя на дъгите на ориентиран граф, а после списък от тези дъги и техните дължини.Списъкът се състои от не повече от 100 дъги, зададени с двойки номера на върхове (начало, край) и дължината на дъгата. Върховете на графа са номерирани с последователни цели положителни числа, започвайки от 1. Входът съдържа много примери.

Изход:
За всеки пример на нов ред се отпечатва редица от дължините на минималните пътища от връх с номер 1, номер 2 и т.н. до всички върхове последователно, според номерацията на върховете. Ако няма път се отпечатва -1. Примерите се отделят с празен ред.

Пример:
3
1 2 1
2 3 1
1 4 2
2
1 2 4
2 1 5

Решение на примера:
0 1 2 2
-1 0 1 -1
-1 -1 0 -1
-1 -1 -1 0

0 4
5 0

---

Задача 9b. [5.4.4, стр. 282] tsp.c
Да се реши задачата за търговския пътник (Хамилтонов цикъл с минимална дължина) за неориентиран граф с не повече от 40 върха.

Вход:
На входа се задава най-напред броя на ребрата на неориентиран граф, а после списък от тези ребра и техните дължини. Списъкът се състои от не повече от 1000 ребра, зададени с двойки номера на върхове и дължината на реброто. Върховете на графа са номерирани с последователни цели положителни числа, започвайки от 1. Входът съдържа много примери.

Изход:
За всеки пример на един ред се отпечатва списък (редица) от върховете на графа, получени при обхождането му. Първият член на редицата трябва да бъде 1. Ако не съществува цикъл се отпечатва -1.

Пример:
5
1 2 1
2 3 2
1 4 2
2 4 4
3 4 1
3
1 2 1
2 3 2
1 4 2

Решение на примера:
1 2 3 4
-1

---