'''Task 104. Find the most valuable path in the weighed non-oriented graph.
The value of path is calculated as the product of weights of graph edges.

The used algorithm deals with Diixtra approach. It represents the breadth-first search.
The code is detailed, has comments, some duck tapes, is not optimized and so on.
'''

import operator as op

def task104(N, roads):
    # Constructing adjacency matrix for graph
    V = [[0] * N for _ in range(N)]
    for road in roads:
        V[road[0] - 1][road[1] - 1] = road[2] / 100.
        V[road[1] - 1][road[0] - 1] = road[2] / 100.

    # Constructing auxiliary arrays:
    # - values is an array of survival probabilities for every crossroad,
    # - paths is an array of optimal paths to every crossroad,
    # - closed is a set of visited graph nodes (crossroads),
    # - order_of_visit is an array which represents the order of visiting graph nodes
    values = [0] * N
    paths = [str(i + 1) for i in range(N)]
    closed = set()
    order_of_visit = []

    # Starting with a node number one
    values[0] = 1
    paths[0] = '1'
    order_of_visit.append(0)

    while order_of_visit:
        # Find the node with maximum survival probability
        order_of_visit.sort(key=lambda i: values[i], reverse=True)
        current = order_of_visit[0]

        # Getting a list of neighbouring nodes sorted by survival probability
        current_roads = sorted(enumerate(V[current]), key=op.itemgetter(1), reverse=True)

        # Visiting neighbour nodes:
        for road in current_roads:

            # Skip node if it is already visited or cannot be visited from the current one
            if road[0] in closed or not road[1]:
                continue

            # Otherwise add node to the visiting queue
            order_of_visit.append(road[0])

            # Survival probability in case we use the current path
            prob = values[current] * road[1]

            # If new probability is more than the existing value, we remember this path:
            if values[road[0]] < prob:
                values[road[0]] = prob
                paths[road[0]] = paths[current] + '-' + str(road[0] + 1)

        # This crossroad is visited
        closed.add(current)
        del order_of_visit[0]

    return values[-1], paths[-1]


roads = [[1, 2, 98], [1, 3, 50], [1, 4, 20], [2, 4, 99], [3, 4, 70]]
print('Chance of survival: {:.2f}, path is \'{}\''.format(*task104(4, roads)))    # (0.97, '1-2-4')

roads = [[1, 2, 98], [1, 3, 97], [1, 6, 15], [2, 4, 99], [2, 5, 100], [3, 4, 70], [4, 6, 99]]
print('Chance of survival: {:.2f}, path is \'{}\''.format(*task104(6, roads)))    # (0.96, '1-2-4-6')

roads = [[1, 3, 99], [3, 5, 70], [2, 5, 99], [2, 4, 98], [4, 6, 86], [5, 7, 47], [6, 7, 77]]
print('Chance of survival: {:.2f}, path is \'{}\''.format(*task104(7, roads)))    # (0.45, '1-3-5-2-4-6-7')