백준 1446. 지름길

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

1446번: 지름길

 

d[i] : i 까지 도달하는데 최소 거리 

 

우선 d[i]는 i 지점까지 도달하는데 최소 거리이기 때문에, 최초에는 d[i] = i 일 것이다. (지름길이 아직 없을때)

 

이제 지름길에 의해 변경되는 값들을 생각해보자. 

지름길의 시작이 from, 도착 지점이 to, 지름길 길이가 distance라고 해보자. 

그렇다면 d[to] 즉 지름길에 의해 도착하는 지점의 값은 원래 의 d[to] 값과, 지름길의 출발 지점의 최소 거리 d[from] + 지름길 길이 distance 중에 작은 값이 된다. 

 

이렇게 d[to]를 구했지만 하나의 지름길에 대하여 d[to] 값만 변경되는 것이 아니다.

d[to] 까지의 최소 거리가 줄어들었다면 d[to] 뒤의 길이들도 그 지름길을 타고 이동할수 있기 때문에 d[to] 부터 길의 끝까지도 모두 변경된다. 

 

이렇게 지름길에 의해 값들을 변경하면 되는데 주의할점이 있다.

주어지는 지름길 값들을 시작지점에 대하여 오름차순으로 정렬하고 위 계산들을 수행해야 한다.