파이썬 알고리즘 199번 | [백준 1939번] 중량제한 - bfs

199. 중량제한

1) 어떤 전략(알고리즘)으로 해결?

• bfs

2) 코딩 설명

<내 풀이>

<내 틀렸던 풀이, 문제점>

6프로에서 틀리는 내풀이

from collections import deque
import sys

#n개의 섬 
n,m = map(int, sys.stdin.readline().rstrip().split())
bridges=[{} for _ in range(n+1)]
visited = [-1 for _ in range(n+1)]
q=deque()

# 인덱스 n = n번째 섬 이 가지는 (다리, 중량)
for i in range(m) :
    a,b,c=map(int, sys.stdin.readline().rstrip().split())
    if b in bridges[a] :
        if bridges[a][b]<c:
            bridges[a][b]=c
            bridges[b][a]=c

    else : bridges[a][b]=c; bridges[b][a]=c

i1, i2=map(int, sys.stdin.readline().rstrip().split())

q.append(i1)
visited[i1]=0

while q:
    now=q.pop()
    for key in (bridges[now]) :
        if visited[key]==-1 :
            visited[key]=visited[now]+bridges[now][key]
            q.append(key)

# print(visited)
print(visited[i2])

(+)

9 9   
1 4 11
1 5 2 
4 5 4 
4 3 10
4 2 7 
5 2 10
5 6 13
3 2 9
2 6 8
1 6  
15

<반성 점>

<배운 점>