[코딩테스트 연습] 배달

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12978

---

기본적인 다익스트라 문제입니다.

 

1. N제한이 크지 않고

2. "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다."

 

위 두 가지 이유 때문에 인접리스트보다 인접행렬로 최소 비용의 간선만 저장하도록 그래프를 구현하였습니다.

 

1번 마을은 무조건 배달이 되므로,

2번 부터 N번 마을까지 다익스트라를 돌려서 dist[N] <= K 인 곳만 세주면 정답이 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter06.cc