6118 : 0-1 BFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개와 간선 M개로 구성되고, 간선의 가중치가 0 또는 1 중 하나인 무방향 그래프가 주어집니다. 1번 노드에서 N번 노드까지 도달하는 데 필요한 최단 거리를 구하는 프로그램을 작성하십시오.
다익스트라 알고리즘보다 빠른 $O(V+E)$ 시간 내에 해결하기 위해, 덱(Deque)을 사용해 가중치가 0인 간선은 덱의 앞에(Front), 1인 간선은 덱의 뒤에(Back) 삽입하는 0-1 BFS 기법을 사용해 구현하십시오.
다익스트라 알고리즘보다 빠른 $O(V+E)$ 시간 내에 해결하기 위해, 덱(Deque)을 사용해 가중치가 0인 간선은 덱의 앞에(Front), 1인 간선은 덱의 뒤에(Back) 삽입하는 0-1 BFS 기법을 사용해 구현하십시오.
입력 설명
첫째 줄에 N (1 ≤ N ≤ 1,000)과 M (0 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 간선 정보 u, v, w가 주어집니다. (w는 0 또는 1)
둘째 줄부터 M개의 줄에 간선 정보 u, v, w가 주어집니다. (w는 0 또는 1)
출력 설명
1번 정점에서 N번 정점까지의 최단 거리를 출력합니다. 도달할 수 없다면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2 1
2 3 1
3 4 1
1 3 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
일반 큐 대신
collections.deque를 활용하여 갱신 조건 만족 시 가중치가 0이면 appendleft()를, 1이면 append()를 호출하여 최단 거리를 갱신합니다.