[BOJ]13308번: 주유소

 

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

---

jason님 풀이를 바탕으로 해결하였습니다. (https://jason9319.tistory.com/249)

 

거리와 비용 최소화라는 2가지 정보로 판단해야 합니다.

그렇기 때문에 단순히 dist[N] 1차원 배열로는 모든 정보를 담을 수 없습니다.

그래서 dist[N]과 같은 역할을 하는 2차원 dp테이블을 사용합니다.

 

dp[node][minOilCost] 정의

: 1번 노드부터 순회하여 node까지 왔고, 지금까지 방문한 주유소의 기름 가격 중 최소 기름 가격

 

그리고 이 dp table에 node를 방문하며 쌓인 totalCost 값을 집어넣는 것입니다.

dp[node][minOilCost] = totalCost

 

이런식으로 다익스트라를 돌고 N번째 노드에 도착하면 순회를 종료하는 것입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13308.cc