글 읽기 - 1916 질문입니다...이게 왜 틀리는 걸까요...

chlrltjd5263 2년 전 0

왜 틀리게 나오는지 잘 모르겠습니다... 아무리 생각해도 모르겠고, 참조된 답도 넣어봤는데 다를 게 뭔지 싶네요 ㅠㅠ

import sys
N = int(sys.stdin.readline())
vtx = [i for i in range(N)]
INF = 1000000000000000000000
adj = [[INF for i in range(N)]for i in range(N)]
for i in range(N):
    adj[i][i] = 0
M = int(sys.stdin.readline())
for i in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    adj[A-1][B-1] = C

def choose_vertex(dist,found):
    global INF
    min = INF
    minpos = -1 
    for i in range(len(dist)):
        if dist[i] < min and found[i] == False:
            min = dist[i]
            minpos = i
    return minpos 

def shortest_path_dijkstra(vtx, adj, start, end):
    vsize = len(vtx)
    dist = list(adj[start]) 
    found = [False]*vsize
    found[start] = True
    dist[start] = 0

    for _ in range(vsize-1): 
        u = choose_vertex(dist,found)
        found[u] = True
        if u == end:
            break

        for w in range(vsize):
            if not found[w]:
                if dist[w] > dist[u] + adj[u][w]:
                    dist[w] = dist[u] + adj[u][w]

    print(dist[end])

Start, End = map(int, sys.stdin.readline().split())
shortest_path_dijkstra(vtx,adj,Start-1,End-1)

ludwings 2년 전 1

경로중에

1 2 3

1 2 5

두개가 존재한다면?

chlrltjd5263 2년 전 0

감사합니다 ㅠㅠ 덕분에 반례 찾았네요

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

문제

문제

출처

ICPC

1916 질문입니다...이게 왜 틀리는 걸까요...

chlrltjd5263 2년 전 0

ludwings 2년 전 1

chlrltjd5263 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말