주간 문제풀이 16 (BOJ 9323)

BOJ 9323 - 무임승차

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

9323번: 무임승차

기차를 탈 때 티켓 요금과 무임승차 벌금을 고려하여 출발지에서 도착지까지의 최소 기댓값을 구하는 문제.

풀이:

우선, n개의 도시를 거치는 표를 사는 것을 마치 n-1개의 독립적인 표를 사되, 첫 도시에서만 s원을 내야 하는 것처럼 생각할 수 있다. 이렇게 생각하게 되면 아래와 같은 점화식을 뽑을 수 있다.

dp[i][0] = i번 노드까지 도착했고, 여기서 출발하며 표를 산다면 s원을 안내도 됨

dp[i][1] = i번 노드까지 도착했고, 여기서 출발하며 표를 산다면 s원을 내도 됨

 

그 후에는 이제 n*2개의 노드 위에서 다익스트라를 돌리면 된다. 표를 사는 간선이라면 두번째 차원이 0인 곳으로 가는 것이고, 표를 사지 않는 간선이라면 두번째 차원이 1인 위치로 가는 것이다.

코드: http://boj.kr/c77911f4550e46d9b4afbc5c4e4f796f