글 읽기 - 해당 문제 플로이드-워셜로도 풀리기는 합니다.(코드 주의)

songmin9813 2년 전 4

파이썬 기준입니다.

다만, 로직을 약간 변경해서 플로이드를 한 번 돌린 다음에 dist[i][i]<0을 찾는 것이 아니라(이러면 시간초과)

플로이드를 돌리는 도중에 dist[i][i]<0을 만족하는 순간 YES를 출력하고 탈출하게 하면 AC 나옵니다.

def floyd(dist, n):
    for middle in range(1,n+1):
        for start in range(1,n+1):
            for end in range(1,n+1):
                if dist[start][end]>dist[start][middle]+dist[middle][end]:
                    dist[start][end]=dist[start][middle]+dist[middle][end]
                    if start==end and dist[start][end]<0:
                        return True
    return False

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해당 문제 플로이드-워셜로도 풀리기는 합니다.(코드 주의)

songmin9813 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말