[Python]최단경로 백준 10217

   문제

   https://www.acmicpc.net/problem/10217

냅색과 다익스트라의 혼합문제 정도 되는거같다.

처음엔 최소힙을 사용하여 구현하였으나 시간초과가 나왔다. 쓸데없는 부분에서 너무

많은 탐색을 하는거같다.그냥 순서대로 모두 확인하는 방법이 나을거같다.

비용을 열로 두고 도착지점을 행으로 둔 메트릭스를 하나 만들고 DP를 이용해 풀어보자.

비용이 더 줄어들수는 없기때문에 비용이 0~M까지 차례대로 도착지점을 확인하며 DP에

 소요시간을 넣어주면 된다.간단한 예시를 통해 보면 이해하기 쉽다.

1

4 10 6

1 2 3 3

1 3 6 8

1 4 9 13

2 3 3 4

2 3 7 3

3 4 4 5

먼저 비용이 10까지 이고 도착지가 4개 있으므로 5행10열의 배열을 만들어준다.

첫줄은 입력의 편의를 위해 사용한것으로 의미가 없다.

배열을 모두 inf로 초기화시킨뒤 1에서 출발하므로 1,0의 값을 0으로 초기화시킨다.

1->1로 가는 비용이 0일때 소요시간이 0이라는 뜻이다.

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf inf  inf inf inf inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

이제 열(비용이 0~M)까지의 순서대로 살펴보자

비용이 0일때는 1에서 출발하는 방법밖에없다

1->2 비용이 3이 드므로 [2][3]에 소요시간 3의 값을 넣어준다.

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

1에 연결된 나머지 티켓도 확인하여 넣어준다.

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf 8 inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf 8 inf inf inf inf

inf inf inf inf inf inf inf inf inf 13 

비용이 1,2일때는 없으므로 넘어가고

3일때를 살펴보자. 

비용이 3일때 2로 도착하는 경우가 있다.

2에서 출발할수 있는경우를 찾아보자

2 3 3 4

2 3 7 1

각각 구해보면 3으로 갈때 

비용이 6들고 7의 시간이 소요

비용이 10들고 4의 시간이 소요

각각 [3][6]=7 ,[3][10]=4에 값을 추가해준다.

이때 [3][6]에 있는값이 8인데 7이 더작으므로 갱신해준다.

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf 7 inf inf inf inf

inf inf inf inf inf inf inf inf inf 13 inf

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf 7 inf inf inf 4

inf inf inf inf inf inf inf inf inf 13 inf

다시 비용이 4일때부터 쭉 찾아준다.

비용이 6일때 3으로 도착하는 경우가있다.

3에서 출발하는 경우를 찾아보자

3 4 4 5

4로가는 경우 비용이 10이 들고 소요시간이 12이다.

[4][10]=12로 갱신해준다.

다시 뒤에 비용들을 보자 [4][9]와 [4][10]이 있지만 도착지점이므로 더이상 출발하는 

경우를 찾을필요는없다.

비용이 10일때 3에 도착하는 경우가 있지만 비용이 초과하는경우는 기록하지 않는다.

inf inf inf inf inf inf inf inf inf inf inf

0 inf inf inf inf inf inf inf inf inf inf

inf inf inf 3 inf inf inf inf inf inf inf

inf inf inf inf inf inf 7 inf inf inf 4

inf inf inf inf inf inf inf inf inf 13 12

이렇게 모든 경우의 수를 살펴본뒤 4로 도착하는 경우인 4행에서 가장 작은 소요

시간을 골라주면된다.

코드를 작성할때 배열부분에서 조금 헷갈리는 부분이 있지만 충분히 구현할수 있을것

이다.

import sys
 
T=int(input())
INF=sys.maxsize
 
for _ in range(T):
    N,M,K=map(int,sys.stdin.readline().split())#공항수,지원비용,티켓정보수
    ticket=[[] for _ in range(N+1)]
    for _ in range(K):
        u,v,c,d=map(int,sys.stdin.readline().split())#출발,도착,비용,소요시간
        ticket[u].append([v,c,d])
 
 
    DP=[[INF for _ in range(M+1)] for _ in range(N+1)]#열:비용 행:n까지갈때
    DP[1][0]=0#1->1로 갔을때 비용은0 시간도 0
 
    for c in range(M+1):
        for d in range(1,N+1):
            if DP[d][c]==INF:continue#c의 비용으로 d에 도착하는 경우가 없다면
            t=DP[d][c]#c의 비용으로 d에 도착햇을때의 소요시간
            for dv,dc,dd in ticket[d]:#d에서 출발하는 모든경우
                if dc+c>M:#비용이 초과될경우 넘어간다
                    continue
                DP[dv][dc+c]=min(DP[dv][dc+c],t+dd)#이전에 저장된값과 비교하여 작다면 갱신해준다
 
    result=min(DP[N])#N에 도착할때 최소소요시간
 
    if result==INF:
        print('Poor KCM')
    else:
        print(result)

 파이썬으로 통과하지 못하였고 pypy3를 통해서 통과할수있었다.

정답자중 파이썬으로 통과한 사람도 있었다.

최소힙을 사용하여 구현한거 같은데 파이썬으로 통과 할수 있도록 도전해봐야겠다.