11779 최소비용 구하기 2

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

다익 + 경로추적 문제

전통적인 다익이 아닌, 우선순위큐 다익으로 시간을 줄였다

경로추적은 부모배열을 이용하고,

거리최소값이 갱신될 때, 갱신된 정점의 부모를 방문 정점의 부모로 설정해주면 된다

증명은 안했음, proved by ac

다익 우선순위큐로 하는법과 역추적

- pair 자료구조에 compareTo 함수를 만든다, 간선값으로 오름차순정렬되도록 this.w - o.w 를 이용한다

- 맨처음 start 정점의 dist 값을 0으로 설정 후, PQ에 pair를 집어넣는다.

- 인접 정점에 대해서 검사를 하는데, dist값이 갱신될 때, PQ에 pair를 집어 넣어주는게 포인트다 (존나 중요함)

- 이는 전통 다익에서 dist 배열값 갱신 마무리하고 그다음 제일 최단거리 정점 방문하는 것과 같은 효과를 낸다

- 그래서 while문 내부에서 방문했는지에 대한 검사를 계속 해준다

- 추적용 parent배열은 dist값이 갱신될 때, 갱신된 인접정점의 부모값을 현재 방문 정점으로 설정한다.

- 그 후 다익이 끝났으면 end에서부터 역추적해서 루트까지 가고, 마지막에 시작 정점까지 추가해준다

김심야 팬