목록BFS (1)
블로그 옮겼습니다
BOJ 3526번 이상적인 경로
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{c}\leq{10^9}\) 노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.두 노드 사이에 엣지는 여러개 있을 수 있다.출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면사전순으로 앞서는 sequence 를 구하는 문제이다. 우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서색의 seqeunce 를 구해주면 될..
Algorithm/Problem Solving
2017. 5. 7. 16:35