백준 2157. 여행

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

2157번: 여행

 

이동은 작은번호에서 큰 번호 만 가능하다고 했기 때문에 입력을 받을때 큰번호->작은번호는 저장 자체를 안해주면 된다.

 

기본적으로 다익스트라처럼 d[i] 에 i번 노드에 도착했을때 먹을수 있는 최대 기내식을 저장하고,

다음 노드로 이동했을때 기내식 점수를 계산해서 d 에 저장되어 있는 점수보다 작다면 이동하지 않으면 된다.

 

하지만 이 문제에서 조심해야 할 부분은 총 M개의 노드만 방문할수 있다는 점이다.

위의 조건만으로 이동하게 되면 M개의 노드를 모두 방문했는데 노드 N 에 도착하지 못할수도 있다.

 

따라서 이 문제는 d[] 가 아닌 d[i][j] 2차원 배열을 만들어야 한다.

d[i][j] : 노드 i 에 j 번째로 도착했을때 먹을수 있는 최대 기내식.

 

다음 노드 이동은 d[nextNode][depth+1] < d[curNode][depth] + nextDist 를 만족할때만 이동하면 된다.