글 읽기 - 어디서 틀렸는지 모르겠습니다

vs6641 1년 전 0

일단 성공은 했는데, 주석을 기준으로 위의 코드는 성공을 하였고, 아래 코드는 실패하였습니다.

위와 아래는 li를 만드는 과정과 bfs함수 내의 for문에서 살짝 다른데, 결국 같은 뜻을 한다고 생각하는데 왜 아래 코드는 실패하는지 이유를 모르겠습니다.

import sys
from collections import deque
n = int(sys.stdin.readline())
li = [[] for _ in range(n+1)]
for _ in range(n):
    s = list(map(int, sys.stdin.readline().split()))
    for i in range(1, len(s) - 2, 2):
        li[s[0]].append((s[i], s[i + 1]))
        
def bfs(x):
    visited = [0] * (n+1)
    mx = [0, 0]
    visited[x] = 1
    queue = deque()
    queue.append([x, 0])
    
    while queue:
        j = queue.popleft()
        for a, b in li[j[0]]:
            if visited[a] == 0:
                visited[a] = 1
                queue.append([a, j[1] + b])
                
                if mx[1] < j[1] + b:
                    mx = [a, j[1] + b]
    return mx

a = bfs(1)
print(bfs(a[0])[1])


##########################################################

"""
import sys
from collections import deque
n = int(sys.stdin.readline())
li = [[]] + [list(map(int, sys.stdin.readline().split()))[1:-1] for _ in range(n)]
def bfs(x):
    visited = [0] * (n+1)
    mx = [0, 0]
    visited[x] = 1
    queue = deque()
    queue.append([x, 0])
    
    while queue:
        j = queue.popleft()
        for i in range(0, len(li[j[0]]) - 1, 2):
            
            if visited[li[j[0]][i]] == 0:
                visited[li[j[0]][i]] = 1
                queue.append([li[j[0]][i], j[1] + li[j[0]][i+1]])
                
                if mx[1] < j[1] + li[j[0]][i+1]:
                    mx = [li[j[0]][i], j[1] + li[j[0]][i+1]]
    return mx

a = bfs(1)
print(bfs(a[0])[1])
"""

flyjb 1년 전 2

간선 정보가 주어질때, 정점 번호 순서로 주어지지 않을 수 있어서 아래 코드가 틀린 것 같네요.

아래는 반례입니다.

입력:

5
5 4 6 -1
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1

윗 코드:

아랫 코드:

vs6641 1년 전 0

입력이 순서대로 들어오는 줄 알고 풀었네요... 감사합니다!

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다

vs6641 1년 전 0

flyjb 1년 전 2

vs6641 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말