import sys
input = sys.stdin.readline
def DFS(now,bit,cnt):
if graph[now][0] >= cnt:
DP[now][bit] = cnt
for next in range(1,K+1):
if bit&(1<<next) or graph[now][next]<cnt:
continue
if not DP[next][bit|(1<<next)]:
DFS(next,bit|(1<<next),cnt+1)
DP[now][bit] = max(DP[now][bit],DP[next][bit|(1<<next)])
def makegraph():
newgraph = [[0]*(K+1) for i in range(K+1)]
for i in range(K+1):
for j in range(K+1):
newgraph[i][j] = graph[jewel[i]][jewel[j]]
return newgraph
N,M,K = map(int,input().split())
jewel = [0]+[int(input())-1 for i in range(K)]
graph = [[-1]*N for i in range(N)]
for i in range(M):
x,y,w = map(int,input().split())
graph[x-1][y-1] = graph[y-1][x-1] = w
for i in range(N):
graph[i][i] = 100
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][j] < min(graph[i][k],graph[k][j]):
graph[i][j] = min(graph[i][k],graph[k][j])
graph = makegraph()
result = 0
DP = [[0]*(1<<(K+1)) for i in range(K+1)]
DFS(0,1,0)
print(DP[0][1])
비트마스킹을 이용한 DP + 플로이드 워셜을 이용하여 해결하였다.
풀이를 우선 설명하면,
1. 플로이드 워셜을 이용하여, 모든 섬 간에 그래프를 찾아준다. 이때 그래프의 갱신은 간선의 가중치의 최솟값의 크기가 클 때 일어난다.
2. 보석이 있는 K개의 섬과 1번 섬을 가지고 그래프를 간소화시킨다. (N*N 크기의 인접행렬을 (K+1)*(K+1)로 간소화)
3. 외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 방식으로 비트마스킹을 이용한 DP로 순회할 수 있는 섬의 최댓값을 구한다.
4. 결과를 출력한다.
문제에서 N의 크기가 최대 100으로 매우 작기 때문에 플로이드-워셜을 응용해서 섬간에 이동할 수 있는 최대보석개수를 찾는것이 핵심이다. 이것만 성공하면, 이후는 외판원 순회 문제를 풀었다면 쉽게 해결할 수 있다.
오늘의 교훈) N이 작을떄는 플로이드-워셜이 최고다