이번 문제는 DP를 통해 해결하였다. 처음에는 다익스트라를 통해 힙에 점수에 해당하는 값을 음수로 넣어 최대힙으로 구현하여 해결하려고 했으나 오답이라는 결과를 얻었다. 그래서 DP로 다시 구현하였다. 비행에 해당하는 그래프를 인접 행렬로 구현하고, dp 리스트를 2차원 리스트로 구현하였다. 이때 두번째 인덱스는 도착했던 도시의 갯수에 해당하게 된다. 우선 dp[1에서 갈 수 있는 도시][2]를 비행 그래프를 보고 갱신한다. 그 후에 점화식을 이용하여 dp를 갱신한다. 점화식은 다음과 같다.

for i in range(2, n+1):
    for j in range(3, m+1):
        for l in range(1, i):
            if airline[l][i] and dp[l][j-1]:
                dp[i][j]=max(dp[l][j-1]+airline[l][i], dp[i][j])

i는 도시들을 의미하고, j는 방문한 도시의 갯수를 의미하게 된다. l은 i로 갈 수 있는 도시를 의미한다. dp[i][j]를 갱신하기 위해서는 l에서 i로 가는 항공편이 있어야 하고, dp[l][j-1] 즉, l까지 갔을 때 이전 방문 도시 수가 m보다 작은 범위에 있어야 한다.

• n, m, k를 입력받는다.
• 항공편에 해당하는 리스트 airline을 (n+1)*(n+1)의 크기로 선언하고 0으로 채운다.
• dp리스트를 (n+1)*(m+1)의 크기로 선언한다.
• k번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> airline[a][b]를 airline[a][b]와 c 중 더 큰 값으로 갱신한다.
• 2부터 n까지의 i에 대한 for문을 돌린다.
  -> 3부터 m까지의 j에 대한 for문을 돌린다.
  --> 1부터 i-1까지의 l에 대한 for문을 돌린다.
  ---> 만약 airline[l][i]가 0이 아니고, dp[l][j-1]이 0이 아닐 경우,
  ----> dp[i][j]를 dp[l][j-1]+airline[l][i]와 dp[i][j] 중 더 큰 값으로 갱신한다.
• dp[n]에서의 최댓값을 출력한다.

Code

import sys
input=sys.stdin.readline
n, m, k=map(int, input().split())
airline=[[0]*(n+1) for _ in range(n+1)]
dp=[[0]*(m+1) for _ in range(n+1)]
for _ in range(k):
    a, b, c=map(int, input().split())
    airline[a][b]=max(airline[a][b], c)
for i in range(2, n+1):
    dp[i][2]=airline[1][i]
for i in range(2, n+1):
    for j in range(3, m+1):
        for l in range(1, i):
            if airline[l][i] and dp[l][j-1]:
                dp[i][j]=max(dp[l][j-1]+airline[l][i], dp[i][j])
print(max(dp[n]))