Big Macs Around the World

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

"""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()

• Dependency: teflib.tgraph.spfa