one Book a Day

시작정점을 어디로 두어야 하는가? 초기 최단거리값을 float('inf)가 아닌 정수로 두어야 하는 이유가 무엇인가? 두가지에 대해 고민해볼 필요가 있는 문제 두 가지 조건에 따라 시작 지점에서 도달 할 수 있는 또는 도달할 수 없는 음수 사이클 판별 가부가 결정된다. import sys input = sys.stdin.readline def bellman_ford(start): dists[start] = 0 for cycle in range(n): for cur_node, next_node, cost in edges: if dists[cur_node] + cost < dists[next_node]: dists[next_node] = dists[cur_node] + cost if cycle == n - ..

확률을 인자로 넘기는 백트래킹. def dfs(row, p): global max_p if row == N: max_p = p return for col in range(N): next_p = p * P[row][col] if not col_check[col] and next_p > max_p: col_check[col] = True dfs(row + 1, next_p) col_check[col] = False for test in range(1, int(input()) + 1): N = int(input()) P = [list(map(lambda x: int(x) / 100, input().split())) for __ in range(N)] col_check = [False] * N max_p = 0..