글 읽기 - 다익스트라 파이썬 반례 부탁드려요

83tachyon 4년 전 0

안녕하세요

아래의 코드로 제출했을 때 '틀렸습니다'라고 나옵니다.

혹시 반례를 찾아주실 수 있으신가요?

def main():
    nEdges = int(input().split()[1])

    # setting up the graph
    graph = {}
    for _ in range(nEdges):
        start, goal, weight = map(int, input().split())
        if start not in graph:
            graph[start] = {}
        if goal not in graph:
            graph[goal] = {}
        graph[start][goal] = weight
        graph[goal][start] = weight

    # path travel and output
    for start in graph:
        Manager.reset(graph)
        Manager.costTable[start] = 0
        graphCopy = dict(graph)
        pathTraveler(graphCopy)
        for goal in graph:
            if start == goal:
                print('-', end=' ')
                continue
            while Manager.traceTable[goal] != start:
                goal = Manager.traceTable[goal]
            print(goal, end=' ')
        print()


class Manager:
    costTable = {}
    traceTable = {}

    @classmethod
    def reset(cls, g):
        for vertex in g:
            cls.costTable[vertex] = float('inf')
            cls.traceTable[vertex] = '-'


def pathTraveler(g):
    # dijkstra algorithm
    # the important point is that next start vertex would be the one with smallest cost!
    while g:
        start = None
        for vertex in g:
            if start == None:
                start = vertex
            elif Manager.costTable[start] > Manager.costTable[vertex]:
                start = vertex
        for goal, weight in g[start].items():
            newCost = Manager.costTable[start] + weight
            if Manager.costTable[goal] > newCost:
                Manager.costTable[goal] = newCost
                Manager.traceTable[goal] = start
        g.pop(start)
    return


main()

gcc 4년 전 1

https://www.acmicpc.net/board/view/44044

83tachyon 4년 전 0

다시 한번 감사드립니다

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

문제

문제

출처

ICPC

다익스트라 파이썬 반례 부탁드려요

83tachyon 4년 전 0

gcc 4년 전 1

83tachyon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말