BOJ 1884 - 고속도로

문제 링크

---

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

문제 해결

---

 1. 다익스트라에서 돈이라는 개념이 들어간 문제. 

주의할 점 || 생각해볼 점

---

 1. dist[i][j] : 정점 i 에서 j만큼 돈을 소모한 상태일 때의 거리. (원래 다익스트라에선 일차원 배열로 선언한다.)

 2. 정점 N을 만나면 바로 종료한다. 

① 정점 N에서 바로 종료하지 않았을 때.

    ② 정점 N에서 바로 종료했을 때

                 

      시간과 메모리 모두 확연하게 줄어든다.

참고

---

 - KCM Travel (이 문제와 비슷하다) : https://www.acmicpc.net/problem/10217

※ 정확하고 부드러운 태클은 언제나 환영입니다.