https://www.acmicpc.net/problem/14938
1초 128MB
간선은 양방향 통행이 가능하고, 길이는 1이상 15이하 노드에 가중치 있음.
시작 지점으로부터 m거리 이내의 노드는 전부 방문 가능하다고 할때 최대 노드 가중치를 구하라. (시작 위치는 어디서든 가능)
첫째 줄에 노드 개수 n, 수색범위 m, 간선 개수 r (1≤ n ≤ 100) (1 ≤ m ≤ 15) (1 ≤ r ≤ 100)
둘째 줄에 n개의 숫자로 각 노드의 가중치 (1이상 30이하)
셋째 줄 부터 간선 정보 a, b, I (노드, 노드, 간선 가중치) (1 ≤ I ≤ 15)
노드 번호는 1부터 n이하의 정수이며, 중복 없음.
얻을 수 있는 최대 노드 가중치
모든 노드에 대한 모든 거리 문제라서 다익스트라를 쓸지 플로이드 워셜을 쓸지 고민했는데, 이 문제는 그냥 플로이드 워셜 복습할겸 플로이드워셜로 풀었다.