BOJ - 7577 - 탐사

import sys

_INF = 1e9
def solution():
    K, N = map(int, sys.stdin.readline().split())
    matrix = [[_INF for _ in range(41)] for _ in range(41)]

    for i in range(K+1):
        for j in range(K+1):
            if i == j: matrix[i][j] = 0
            else: continue

    for i in range(K):
        matrix[i + 1][i] = 0
        matrix[i][i + 1] = 1

    for _ in range(N):
        x, y, r = map(int, sys.stdin.readline().split())
        if matrix[x-1][y] > r: matrix[x-1][y] = r
        matrix[y][x-1] = -r

    for k in range(K+1):
        for i in range(K+1):
            for j in range(K+1):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    for i in range(K+1):
        if matrix[i][i] < 0:
            print("NONE")
            return

    ret = ''
    for i in range(K):
        ret += '#' if matrix[0][i+1] - matrix[0][i] > 0 else '-'

    print(ret)

solution()

https://www.acmicpc.net/problem/7577