Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- nodes = []
- with open('in.txt', 'r') as in_file:
- input_data = [line.strip() for line in in_file.readlines()]
- n = int(input_data[0])
- for i in range(1, n + 1):
- nodes.append(input_data[i].split())
- for j in range(len(nodes[i-1])):
- if int(nodes[i-1][j]) == 32767:
- nodes[i - 1][j] = -32767
- start_point = input_data[n + 1]
- finish_point = input_data[n + 2]
- prev_nodes = [-1] * n
- valid = [True] * n
- weight = [-32767] * n
- weight[int(start_point) - 1] = 32767
- for i in range(n):
- max_weight = -1
- ID_max_weight = -1
- for j in range(len(weight)):
- if valid[j] and weight[j] > max_weight:
- max_weight = weight[j]
- ID_max_weight = j
- valid[ID_max_weight] = False
- for j in range(n):
- if valid[j]:
- alt = max(weight[j], min(weight[ID_max_weight], int(nodes[ID_max_weight][j])))
- if alt > weight[j]:
- weight[j] = alt
- prev_nodes[j] = ID_max_weight
- if weight[int(finish_point) - 1] == -32767:
- with open('out.txt', 'w') as out_file:
- out_file.write('N')
- else:
- path = []
- current_node = int(finish_point) - 1
- while current_node != int(start_point) - 1:
- path.append(current_node + 1)
- current_node = prev_nodes[current_node]
- path.append(int(start_point))
- path.reverse()
- with open('out.txt', 'w') as out_file:
- out_file.write('Y\n')
- for node in path:
- out_file.write(str(node) + ' ')
- out_file.write('\n' + str(weight[int(finish_point)-1]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement