[백준] 1865 웜홀 python

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

1865번: 웜홀

이전 문제와 같이 벨만포드 알고리즘을 사용한 문제이다.

edge를 그대로 넣고 사용할수도 있고 연결 그래프를 만들어서 사용할수도 있다. 뭐가 좋을진 문제마다 다를 것 같지만 이 문제에서는 edge를 사용하는게 조금 더 빠르다. 그래프를 사용하면 필요없는 곳까지 반복해야해서 시간이 더 걸리는 듯하다.

1) edge

# import sys; input = sys.stdin.readline
INF = 987654321
def bf(start):
    global N, M, edges, dist

    dist[start] = 0
    for i in range(N):
        for cur, next, cost in edges:
            if dist[next] > dist[cur] + cost:
                dist[next] = dist[cur] + cost
                if i == N - 1:
                    return True
    return False


def main():
    global N, M, edges, dist
    answer = []
    for tc in range(int(input())):
        N, M, W = map(int, input().split())
        edges = []
        dist = [INF for _ in range(N + 1)]

        for _ in range(M):
            s, e, t = map(int, input().split())
            edges.append((s, e, t))
            edges.append((e, s, t))
        for _ in range(W):
            s, e, t = map(int, input().split())
            edges.append((s, e, -t))

        cycle = bf(1)
        if cycle:
            answer.append("YES")
        else:
            answer.append("NO")
    print("\n".join(answer))


if __name__ == "__main__":
    main()

2) graph

# import sys; input = sys.stdin.readline
INF = 987654321
def bf(start):
    global N, M, g, dist

    dist[start] = 0
    for i in range(N):
        for cur in range(1,N + 1):
            for next, cost in g[cur]:
                if dist[next] > dist[cur] + cost:
                    dist[next] = dist[cur] + cost
                    if i == N - 1:
                        return True
    return False


def main():
    global N, M, g, dist
    answer = []
    for tc in range(int(input())):
        N, M, W = map(int, input().split())
        g = [[] for _ in range(N + 1)]
        dist = [INF for _ in range(N + 1)]

        for _ in range(M):
            s, e, t = map(int, input().split())
            g[s].append([e, t])
            g[e].append([s, t])
        for _ in range(W):
            s, e, t = map(int, input().split())
            g[s].append([e, -t])

        cycle = bf(1)
        if cycle:
            answer.append("YES")
        else:
            answer.append("NO")
    print("\n".join(answer))


if __name__ == "__main__":
    main()