글 읽기 - dfs와 다익스트라의 반례가 무엇일까요??

huisam 5년 전 0

dfs로 vertex에 있는 모든 edge들을 검사하여

도착지에 도달했을 때, 방문한 노드의 수와 가중치를 리스트로 저장하게 했는데 반례를 찾지 못하여 헤매고 있습니다ㅠㅠ

어떻게 하면 제 코드를 개선시킬 수 있을까요??

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,r = map(int, input().split())
e = [[0 for i in range(n+1)] for i in range(n+1)]
v = [[]for i in range(n+1)]
ans = []


def dfs(now, sum, cnt, vertex):
    if now == n:
        ans.append([sum,cnt])
        return
    if not v[now]:
        return
    else:
        while(vertex[now]):
            next = vertex[now].pop(0)
            dfs(next, sum+e[now][next], cnt+1, vertex)


for i in range(r):
    data = list(map(int, input().split()))
    e[data[0]][data[1]] = (data[4] - 10)*data[3] + data[2] if data[4] > 10 else data[2]
    v[data[0]].append(data[1])

dfs(1,0,1,v)

if not ans:
    print("It is not a great way.")
else:
    ans = sorted(ans, key=lambda x: (x[0],x[1]))
    print(ans[0][0], ans[0][1])

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

문제

문제

출처

ICPC

dfs와 다익스트라의 반례가 무엇일까요??

huisam 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말