시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 60 27 16 36.364%

문제

정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제거해 나갈 것이다. 이 때, 특정 정점 s와 t가 비연결이 되는 시점에서 간선 제거를 멈출 것이다. 비연결이란 두 정점이 간선을 통해 방문 불가능한 것을 말한다.

s와 t가 비연결이 되는 시점의 지운 간선의 가중치의 합이 최소가 되게 제거하는 간선의 순서를 조정할 때, 그 최소값을 구하시오.

입력

첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤500,1≤m≤10,000)

다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다.(1≤a,b≤n,1≤c≤100,a≠b)

다음 줄에는 두 정점 s,t가 주어진다.(1≤s,t≤n,s≠t)

출력

s와 t가 비연결되는 시점의 지운 간선의 가중치 합의 최소값을 출력하시오,

예제 입력 1

8 9
1 2 3
1 3 2
1 4 4
2 5 2
3 6 1
4 7 3
5 8 6
6 8 2
7 8 7
1 8

예제 출력 1

6

출처

  • 문제의 오타를 찾은 사람: cs71107