글 읽기 - 33% 에서 안됩니다 반례나 뭐가 틀렸을까요 ?ㅠㅠ

kimkim031 3년 전 0

문자열로 방문한 지점을 저장했습니다..

어디가 잘못됫는지 모르겟어요 ㅠㅠ

from heapq import *
import sys
#input = sys.stdin.readline
INF = sys.maxsize

def Dijkstra(s, sm):
    hq = []
    heappush(hq, (s,str(s)))
    dis = [INF] * (N+1)
    route = [''] * (N+1)
    dis[s] = 0
    route[s] = str(s)
    
    while hq:
        cur, r = heappop(hq)
        for nxt, cost in R[cur]:
            if dis[nxt] > dis[cur] + cost:
                dis[nxt] = dis[cur] + cost
                route[nxt] = route[cur] + str(nxt)
                heappush(hq,(nxt, route[nxt]))
            if dis[nxt] == dis[cur] + cost:
                if (sm in route[cur] + str(nxt)) or (sm[::-1] in route[cur] + str(nxt)):
                    route[nxt] = route[cur] + str(nxt)
            
    tmp = []
    for i in range(1, N+1):
        if (sm in route[i]) or (sm[::-1] in route[i]):
            tmp.append(i)

    return tmp
        

for _ in range(int(input())):
    N, M, T = map(int, input().split())
    S, G, H = map(int, input().split())
    
    R = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, d = map(int, input().split())
        R[a].append((b,d))
        R[b].append((a,d))
        
    candidate = []
    for _ in range(T):
        candidate.append(int(input()))
    
    smell = str(G) + str(H)
    ans = []
    for d in Dijkstra(S, smell):
        if d in candidate:
            ans.append(d)
            
    ans.sort()
    for i in ans:
        print(i, end = ' ')

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

문제

문제

출처

ICPC

33% 에서 안됩니다 반례나 뭐가 틀렸을까요 ?ㅠㅠ

kimkim031 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말