6139 : 쌍방향 도로
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
단방향 도로들로 이루어진 국가의 도로망 지도가 주어집니다.
특정 두 도시 A와 B가 서로 상호 도달(A -> B 와 B -> A 왕복이 모두 가능)할 수 있도록 단방향 도로 중 일부를 양방향 통행이 가능하도록 개조(양방향화)하고자 합니다.
개조해야 하는 단방향 도로의 최소 개수를 구하시오.
특정 두 도시 A와 B가 서로 상호 도달(A -> B 와 B -> A 왕복이 모두 가능)할 수 있도록 단방향 도로 중 일부를 양방향 통행이 가능하도록 개조(양방향화)하고자 합니다.
개조해야 하는 단방향 도로의 최소 개수를 구하시오.
입력 설명
첫째 줄에 도시 수 N (1 ≤ N ≤ 1,000)과 단방향 도로 수 M (1 ≤ M ≤ 2,000)이 주어집니다.
둘째 줄부터 M개의 줄에 단방향 도로 u v (u에서 v로 이동 가능) 정보가 주어집니다.
마지막 줄에는 왕복 통신이 가능해야 하는 도시 A와 B가 공백 구분되어 주어집니다.
둘째 줄부터 M개의 줄에 단방향 도로 u v (u에서 v로 이동 가능) 정보가 주어집니다.
마지막 줄에는 왕복 통신이 가능해야 하는 도시 A와 B가 공백 구분되어 주어집니다.
출력 설명
양방향으로 변경해야 하는 단방향 도로의 최소 개수를 출력합니다. 왕복 가능하게 만들 수 없다면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 2
3 2
1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
A->B 최단 경로와 B->A 최단 경로를 0-1 BFS를 사용해 개별 계산하되, u->v 도로를 v->u로 갈 때의 비용을 1로 모델링하고, 두 방향 최단경로에 사용된 개조 도로들의 합집합(Union) 개수를 취하면 해결됩니다.