반드시 거쳐야 하는 송전선
골드 IV의견: 0
한 전력 회사는 \(N\)개의 변전소와 \(M\)개의 양방향 송전선으로 이루어진 전력망을 가지고 있다. 각 송전선은 두 변전소를 잇고, 그 선을 따라 전류를 보내면 \(w\)만큼의 손실이 발생한다.
오늘 점검 대상으로 지정된 특정 송전선 \((A, B)\)가 있다. 발전소가 있는 변전소 \(S\)에서 출발한 점검 전류가 반드시 송전선 \((A, B)\)를 한 번 지난 뒤 관제 센터가 있는 변전소 \(T\)에 도달해야 한다.
이때 발생하는 총 손실의 최솟값을 구하여라. 조건을 만족하는 경로가 없으면 \(-1\)을 출력한다.
송전선 \((A,B)\)는 \(A \to B\) 방향과 \(B \to A\) 방향 어느 쪽으로 지나도 된다. 같은 두 변전소를 잇는 다중 송전선이 있을 수 있고, 자기 루프는 없다.
- \(2 \le N \le 20{,}000\)
- \(1 \le M \le 100{,}000\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10{,}000\)
- \(1 \le S, T, A, B \le N\), \(S \ne T\), \(A \ne B\)
첫째 줄에 \(N\ M\)이 주어진다.
다음 \(M\)개의 줄에 각 송전선의 정보 \(u\ v\ w\)가 주어진다.
마지막 줄에 \(S\ T\ A\ B\)가 주어진다 — 출발 변전소, 도착 변전소, 그리고 반드시 지나야 하는 송전선의 양 끝 변전소이다. 송전선 \((A,B)\)는 입력의 송전선 목록에 적어도 하나 존재함이 보장된다.
조건을 만족하는 최소 총 손실을 한 줄에 출력한다. 불가능하면 \(-1\)을 출력한다.
4 4
1 2 2
2 3 2
1 3 10
3 4 1
1 4 1 3
11송전선 \((1,3)\)을 반드시 지나야 한다. \(1\to 2\to 3\) 대신 직접 \(1\to 3\)(손실 10)을 써야 하므로 \(1\to 3\to 4\)로 \(10+1=11\).
4 2
1 2 1
3 4 1
1 2 3 4
-1출발/도착은 \(\{1,2\}\) 요소에 있고 점검 송전선 \((3,4)\)는 다른 요소에 있어 거칠 수 없으므로 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
반드시 거쳐야 하는 송전선
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
반드시 거쳐야 하는 송전선