ри станцій, в які можна потрапити з станції з номером k (k вводиться з клавіатури). Схема метрополітену має наступний вигляд: В
Рішення:
Якщо вхідні дані представити у вигляді матриці суміжності колій метрополітену, то за допомогою алгоритму знаходження матриці досяжності можна вирішити дану задачу. Вихідні дані: це індекси стовпців матриці досяжності k - того рядка, які в значенні мають 1.
Вихідні дані для даної задачі будуть мати вигляд:
6 {перший рядок - це кількість станцій метро}
0 1 1 1 0 0
0 0 1 0 1 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 1 1 0
Приклад вихідних даних для даного прикладу:
Введіть пункт відправки - 4
5 червня
(Текст програми див. Додаток 6)
Роботи. Пункти з номерами 1,2, ..., N (N <= 50) пов'язані мережею доріг, довжини яких дорівнюють 1. Дороги проходять на різній висоті і перетинаються тільки в пунктах. У початковий момент часу в деяких пунктах знаходяться M роботів. Всі роботи починають рухатися з постійною швидкістю 1. Зупинятися або міняти напрям вони можуть тільки в пунктах. p> a) Потрібно знайти мінімальне час Т1, через яке всі роботи можуть зустрітися в одному пункті, вказати цей пункт або повідомити, що така зустріч неможлива.
b) Якщо зустріч можлива, то знайти час Т2 <= T1, через яке зустріч може відбутися і поза пунктів.
c) Нехай роботам заборонена яка - Або зупинка, і швидкість дорівнює 1 або 2. За цих умов знайти мінімальне час Т, через яке відбудеться їх зустріч, або повідомити, що зустріч неможлива.
Примітки:
В· Для задачі (в) можна вказати, що М дорівнює 2 або 3.
В· При вирішенні завдань (а) і (б) дані про швидкості ігноруються.
Рішення.
Ідея рішення заснована на властивості досяжності однієї вершини з іншої на графі.
Дані про зв'язки між пунктами будемо зберігати в масиві Alink [1 .. n, 1 .. n], елементи якого дорівнюють 0 або 1. Значення Alink [i, j] = 1 говорить про те, що між пунктами i та j є дорога.
В
1
br/>
У двовимірному масиві Aplace [1 .. n, 1 .. m] для кожного робота значеннями, рівними одиниці, будемо вказувати ті населені пункти, в яких даний робот може перебувати в даний момент часу. Пояснимо логіку вирішення на прикладі. Чотири робота перебувають у пунктах 1,2,7,8. br/>
Alink Aplace
1
2
3
4
5
6
7 ...
