Saleman

mail@pastecode.io avatar
unknown
python
a year ago
1.0 kB
5
Indexable
Never
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()