====== Big Macs Around the World ======

===== 풀이 =====
  * 가중치 있는 그래프에서 최단 경로를 찾는 문제이기는 한데, 경로의 길이가 엣지를 지날때 가중치만큼 더해지는 것이 아니라 가중치만큼 곱해지는 형태이다.
  * 그냥 최단경로 알고리즘에서 거리를 갱신하는 부분을 덧셈 대신에 곱셈으로 고쳐써도 돌아가기는 할것 같다.. 하지만 더 간단한 방법은 곱해야 하는 값들에 로그를 씌운 값을 엣지의 가중치로 두는 것이다. 그러면 그냥 덧셈으로 처리하면서 최단 거리를 구하면 되고, 최단 거리를 다 구한 다음에그 값에 exp를 취해주기만 하면 된다.
  * 문제에서 주어진 환율은 1보다 작은 값들도 있으므로, 로그를 씌우면 당연히 음수가 된다. 음수 가중치가 있는 그래프에서 최단 경로를 구하는 것은 [[ps:단일_출발지_최단_경로#shortest_path_faster_algorithm_spfa|SPFA]]를 사용해서 O(VE)에 풀면 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 5942. Big Macs Around the World".

- Problem link: https://www.acmicpc.net/problem/5942
- Solution link: http://www.teferi.net/ps/problems/boj/5942

Tags: [SPFA]
"""

import math
import sys
from teflib import tgraph

INF = float('inf')


def main():
    inp = sys.stdin.readline().split()
    N, M, A, B = int(inp[0]), int(inp[1]), int(inp[3]), int(inp[4])
    V = float(inp[2])
    wgraph = [{} for _ in range(N)]
    for _ in range(M):
        inp = sys.stdin.readline().split()
        i, j, e_ij = int(inp[0]), int(inp[1]), float(inp[2])
        wgraph[i - 1][j - 1] = math.log(e_ij)

    dist = tgraph.spfa(wgraph, A - 1)[B - 1]
    print('0' if dist == -INF else V * math.exp(dist))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:tgraph#spfa|teflib.tgraph.spfa]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}