글 읽기 - 반례 있나여... ㅠㅠㅠ

20wjsdudtj 2년 전 0

계속 14%에서 틀립니다ㅠㅠㅠ

import sys
input=sys.stdin.readline
import heapq

N,M,K,S=map(int,input().split())
P,Q=map(int,input().split())
road=[[] for _ in range(N+1)] #road=[[]]*(N+1) 이거 절대 안 됨 ㅠㅠ
zombie=[int(input()) for _ in range(K)]
for i in range(M):
    a,b=map(int,input().split())
    road[a].append(b)
    road[b].append(a)


def dfs(index,num):
    if num==S: return #이게 더 메모리 적게 씀
    for j in road[index]:
            if not visited[j]:
                visited[j]=1
                dfs(j,num+1)

dp=[float('inf') for _ in range(N+1)]
dp[1]=0
def dijkstra():
    q=[]
    heapq.heappush(q,[0,1])
    while q:
        cost, place=heapq.heappop(q)
        if dp[place]<cost: continue
        for i in road[place]:
            if i in zombie: continue;
            if visited[i] : nextcost=cost+Q
            else: nextcost=cost+P
            if nextcost<dp[i]:
                dp[i]=nextcost
                heapq.heappush(q,[nextcost,i])
    return dp
visited=[0]*(N+1)
for i in zombie: 
    dfs(i,0)

dijkstra()

if visited[N]: print(dp[N]-Q)
else: print(dp[N]-P)


#다익스트라로 위험구간 표시 + dfs
#다익스트라로 1에서 N으로 가는 숙박비 표현 (DP)
#

20wjsdudtj 2년 전 0

아무래도 18번쨰 줄에서 A 좀비 영역과 B 좀비 영역이 겹칠 때가 문제가 생기는 것 같네여!!

근데 18번째 줄을 지우면 시간초과가 나서 그 부분을 deque 써서 풀었더니 해결됐습니다!!

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

문제

문제

출처

ICPC

반례 있나여... ㅠㅠㅠ

20wjsdudtj 2년 전 0

20wjsdudtj 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말