Advertisement
Guest User

Untitled

a guest
Apr 27th, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1. nodes = []
  2. with open('in.txt', 'r') as in_file:
  3. input_data = [line.strip() for line in in_file.readlines()]
  4. n = int(input_data[0])
  5. for i in range(1, n + 1):
  6. nodes.append(input_data[i].split())
  7. for j in range(len(nodes[i-1])):
  8. if int(nodes[i-1][j]) == 32767:
  9. nodes[i - 1][j] = -32767
  10. start_point = input_data[n + 1]
  11. finish_point = input_data[n + 2]
  12. prev_nodes = [-1] * n
  13. valid = [True] * n
  14. weight = [-32767] * n
  15. weight[int(start_point) - 1] = 32767
  16.  
  17. for i in range(n):
  18. max_weight = -1
  19. ID_max_weight = -1
  20. for j in range(len(weight)):
  21. if valid[j] and weight[j] > max_weight:
  22. max_weight = weight[j]
  23. ID_max_weight = j
  24. valid[ID_max_weight] = False
  25. for j in range(n):
  26. if valid[j]:
  27. alt = max(weight[j], min(weight[ID_max_weight], int(nodes[ID_max_weight][j])))
  28. if alt > weight[j]:
  29. weight[j] = alt
  30. prev_nodes[j] = ID_max_weight
  31.  
  32. if weight[int(finish_point) - 1] == -32767:
  33. with open('out.txt', 'w') as out_file:
  34. out_file.write('N')
  35. else:
  36. path = []
  37. current_node = int(finish_point) - 1
  38. while current_node != int(start_point) - 1:
  39. path.append(current_node + 1)
  40. current_node = prev_nodes[current_node]
  41. path.append(int(start_point))
  42. path.reverse()
  43. with open('out.txt', 'w') as out_file:
  44. out_file.write('Y\n')
  45. for node in path:
  46. out_file.write(str(node) + ' ')
  47. out_file.write('\n' + str(weight[int(finish_point)-1]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement