Saleman
unknown
python
2 years ago
1.0 kB
8
Indexable
import collections import sys def myFunc(): INPUT = sys.stdin.readline().strip().split() table = {} for k in range(int(INPUT[0])): u, i, w = sys.stdin.readline().strip().split() if u not in table: table[u] = {} table[u][i] = int(w) frontier = collections.deque([[INPUT[1]]]) cost = collections.deque([0]) end_state = [] end_cost = -1 while frontier: node = frontier.pop() node_cost = cost.pop() if len(node) == len(table)+1: end_state = node end_cost = node_cost continue for i in table[node[-1]].keys(): if (i not in node) or (len(node) == len(table) and i == node[0]): new_cost = node_cost + table[node[-1]][i] if end_cost == -1 or new_cost < end_cost: frontier.append(node + [i]) cost.append(new_cost) print(' '.join(map(str, end_state))) if __name__ == '__main__': myFunc()
Editor is loading...