글 읽기 - 1389번 어디서 틀린지 모르겠습니다.

okc05181 2년 전 0

그래프 라고 생각하고 정렬한 뒤 인덱스 순서대로 읽어가며 최단거리 찾아봤습니다.

올라온 질문글에 있는 반례는 거의 다 해봤다고 생각합니다만 다 통과했습니다.

반례나 잘못된 부분 지적 부탁드립니다.

import sys

def testzero(table):
    N = len(table)
    for i in range(N-1):
        for j in range(1 + i, N):
            if table[i][j] == N+1:
                return False
    return True


def filltable(table):
    N = len(table)
    for i in range(N-1):
        for j in range(1+i, N):
            tempmin = N + 1
            if table[i][j] == N+1:
                temp = min(table[j])
                for k in range(len(table[j])):
                    if table[j][k] == temp:
                        if tempmin > table[i][k] + 1:
                            tempmin = table[i][k] + 1
                            table[i][j] = table[i][k] + 1
                            table[j][i] = table[i][j]


N, M = map(int, sys.stdin.readline().strip().split(' '))
rela = [[] for _ in range(M)]
minVal = M * N
for i in range(M):
    rela[i] = list(map(int, sys.stdin.readline().strip().split(' ')))
    rela[i].sort()
rela.sort()

#table
table = [[N+1 for _ in range(N)] for _ in range(N)]
for i in range(1, N):
    for j in range(M):
        if rela[j][0] == i:
            table[i - 1][rela[j][1] - 1] = 1
            table[rela[j][1] - 1][i - 1] = 1
        elif rela[j][0] > i:
            break
        else:
            continue

while testzero(table) == False:
    filltable(table)

#for i in range(len(table)):
#    print(table[i])

result = 0
minsum = N*N
for i in range(len(table)):
    tmp = sum(table[i]) - (N+1)
    if minsum > tmp:
        minsum = tmp
        result = i + 1
print(result)

samgkgkgk 2년 전 0

플로이드알고리즘은 반복문을 돌릴적에 k -> i -> j 순서로 돌려야지 정답이 나옵니다!!

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

문제

문제

출처

ICPC

1389번 어디서 틀린지 모르겠습니다.

okc05181 2년 전 0

samgkgkgk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말