시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 196 | 66 | 36 | 40.449% |
자랑스러운 대한민국의 산업기능Agent 욱제는 집 떠나와 열차 타고 훈련소로 떠난다.
모두 알다시피 대한민국은 정점이 V개이고 간선이 E개인 선인장 그래프이고, 집은 1번 정점, 훈련소는 V번 정점이다.
하지만 욱제는 Agent를 감히 훈련소로 보내는 대한민국에 환멸을 느끼고, 간선 몇 개에 수류탄을 떨어뜨리기로 한다. 수류탄으로 간선을 터뜨리면 그 간선을 타고 이동할 수 없게 된다.
욱제는 간선 몇 개를 터뜨린 다음 집에서 훈련소로 가는 경로가 없게 하고 싶다. 4월 2일이 오기 전에 빨리, 욱제가 터뜨려야 할 간선의 길이의 합의 최솟값을 구하자.
첫째 줄에 V, E가 주어진다.
둘째 줄부터 E개의 줄에 대한민국을 이루는 그래프의 각 간선이 잇고 있는 두 정점의 번호 x, y와 간선의 길이 d가 공백을 사이에 두고 주어진다.
욱제가 터뜨려야 하는 간선의 길이의 합의 최솟값을 출력한다. 간선을 어떻게 터뜨려도 훈련소로 가는 경로가 존재하면, 권욱제 재입대
를 출력한다.
6 7 1 2 3 2 3 1 3 4 4 4 6 1 6 3 5 5 3 9 5 1 2
3
2번 정점과 3번 정점을 잇고 있는 길이 1의 간선과, 5번 정점과 1번 정점을 잇고 있는 길이 2의 간선을 하나씩 터뜨린다. 그러면 집(1번 정점)에서 훈련소(6번 정점)으로 가는 경로가 없어진다.
Contest > BOJ User Contest > 논산 코드 페스티벌 > 제1회 논산 코드 페스티벌 A번