250: 그냥 4000 * N번 돌리면 되는 말도안되게 쉬운 문제. DIV2인줄...

450: 나는 Dijkstra 한번 돌려서 Shortest Path의 edge만 남겨서 DAG를 만든 다음 위상정렬하면서 DP를 채웠는데(답이 -1인경우는 이 DAG에 가중치 0인게 있는 경우 뿐), 알고보니 그냥 Dijkstra 하면서 DP배열을 같이 채우면 되는거였다.

1000: 모르겠다 ㅎㅎ