Задачи
Задача 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.
И тази година падналият сняг създава проблеми в града Z. с неговите
N кръстовища (номерирани с числата от 1 до N) и М улици. Всяка улица
свързва две кръстовища, като движението по всички улици е двупосочно
и някои кръстовища може да са свързани с повече от една улица.
Улиците свързват кръстовищата така, че от всяко кръстовище може да
се стигне до всяко друго кръстовище. Улиците са доста широки и за да
бъде почистена една улица от снега, чистещата машина трябва да
премине по нея два пъти – по един път във всяка от двете посоки на
улицата. Естествено, градската управа би искала да почисти всички
улици на града с колкото може по-малко разходи и поставила задачата:
да се намери маршрут на чистещата машина, който да започва от
най-близкото до гаража кръстовище (номерирано с числото 1), минава
по всяка улица точно един път във всяка от двете посоки и завършва в
кръстовището, от което е тръгнала, без да губи време и гориво за да
се придвижва по вече изчистеното. Напишете програма, която решава
поставената задача.
Вход:
На първия ред на стандартния вход ще бъде зададен броят на
тестовете. На първия ред за всеки тест са зададени целите числа N и
M, разделени с един интервал (5 ≤ N ≤ 1000, 5 ≤ M ≤ 100000). Всеки
от следващите M реда съдържа по две числа, разделени с един интервал
– два номера на кръстовища, които са свързани с улица.
Изход:
За всеки тестов пример програмата трябва да изведе на един ред на
стандартния изход намерения маршрут – списък от номерата на
кръстовища, през които минава маршрутът, започвайки от върха с номер
1 и завършвайки във върха с номер 1.
Пример:
1
5 6
1 2
1 4
1 5
2 3
3 4
3 5
Решение на примера:
1 2 3 5 1 4 3 2 1 5 3 4 1