간선 서로소 K-경로의 최소 비용
플래티넘 II의견: 0
\(N\)개의 정점과 \(M\)개의 단방향 간선으로 이루어진 그래프가 있다. 각 간선에는 통행 비용이 있고, 각 간선은 최대 한 번만 사용할 수 있다(간선 서로소 경로). 출발지 \(S\)에서 도착지 \(T\)까지 서로 간선을 공유하지 않는 경로 \(K\)개를 보내려고 한다.
\(K\)개의 경로를 만들 수 있으면 그 경로들이 사용하는 간선 비용의 총합의 최솟값을, 만들 수 없으면 -1을 출력하라.
\(2 \le N \le 400\), \(1 \le M \le 3000\), \(1 \le K \le 50\), \(1 \le w \le 10^4\), \(S \ne T\). 같은 \((u,v)\) 간선이 여러 개 있을 수 있다.
첫 줄에 \(N\), \(M\), \(S\), \(T\), \(K\). 다음 \(M\)개의 줄에 간선 \(u\ v\ w\) (정점 \(u\)에서 \(v\)로 가는 비용 \(w\)).
최소 총비용 또는 불가능하면 -1을 한 줄에 출력한다.
4 5 1 4 2
1 2 1
1 3 2
2 4 2
3 4 1
2 3 5
6경로 \(1\to2\to4\) (비용 3)과 \(1\to3\to4\) (비용 3)을 쓰면 간선이 겹치지 않으며 총 비용 6으로 최소이다.
3 1 1 3 1
1 2 5
-1\(1\)에서 \(3\)으로 가는 경로가 존재하지 않으므로 -1.
riseoj 작성
출처 Original
평가 및 의견
간선 서로소 K-경로의 최소 비용
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
간선 서로소 K-경로의 최소 비용