Advertisement
Guest User

Untitled

a guest
Dec 16th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.66 KB | None | 0 0
  1. city = list()
  2. for i in range(5):
  3.     if i == 0:
  4.         city.append([])
  5.     else:
  6.         city.append([0, False])
  7. # Путь между i и j = i + j
  8. # Сначала создаем массив из 4 элементов (0, False)
  9. # В возможных для проведения 1 меропрития городах заменяем флаг на True
  10. # flag означает, есть ли какой-либо путь от 1ого города до этого при n проведенных мероприятий
  11. # на n-ом проведении мероприятия смотрим, из какого города, в котором проводился предыдущий,
  12. # мы можем попасть в город проведения нынешнего. При том сохраняем только путь с минимальным значением времени
  13. # Так как остальные хранить нет смысла.
  14. n = int(input())
  15. a = list(map(int, input().split()))
  16. print(city)
  17. for k in a:
  18.     city[k][1] = True
  19. print(city)
  20. for i in range(n - 1):
  21.     a = list(map(int, input().split()))
  22.     for k in a:
  23.         for i in range(1, 5):
  24.             if city[i][1]:
  25.                 if city[k][1] == False:
  26.                     city[k][0] = city[i][0] + (i + k)
  27.                     city[k][1] = True
  28.                 else:
  29.                     city[k][0] = min(city[k][0], city[i][0] + (i + k))
  30.     for i in range(1, 5):
  31.         if i not in a:
  32.             city[i][0] = 0
  33.             city[i][1] = False
  34.     print(city)
  35. answer = -1
  36. for a, b in city:
  37.     if b < answer or answer == -1:
  38.         answer = b
  39. print(answer)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement