제독 > 문제은행



문제은행

3100 : 제독

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 11 회    시도횟수: 35 회   



미하일 안데르센 드 뤼터는 네덜란드의 역사에서 가장 유명한 제독으로 알려져 있으며 

17세기에 벌어진 영국-네덜란드 전쟁에서 전공을 세웠다.

 

뤼터가 살던 시절에 그래프 이론이 연구되기 시작했고, 제독은 이론을 해전 계획에 자주 이용했다.

바다 위의 중간 지점은 정점으로 나타낼 수 있고

각 중간 지점에서 이동할 수 있는 뱃길은 방향성이 있는 간선으로 나타나 있다

두 중간 지점 W1W2사이에 뱃길 W1 W2는 최대 한 개 있을 수 있다

각 간선의 가중치는 그 뱃길을 안전하게 이동하기 위해 발사해야 하는 포탄의 수이다.

 

뤼터의 가장 유명한 전술은 이름 하여 뤼터작전이다

이 전술은 출발 지점에서 두 전함이 새로 다른 방향으로 출발을 한다

그 다음 적함과 전투를 하면서 이동하여 목적지에서 다시 만나는 전술이다

이 전술에서 두 전함은 항상 겹치지 않는 뱃길을 택해야 하며

출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지날 수 없다.

 

뤼터는 돈을 낭비하는 것을 좋아하지 않는다

그래서 가능한 한 포탄을 가장 적게 발사하는 뱃길을 택하려고 한다.

 

아래 입력 예에 대한 그림과 설명이다. 

 

 28f4845c4023c05a03e41980f6649bed_1497962

두 함선(빨강, 파랑)1에서 시작해서 6에서 만난다.

빨간 함선은 1 3 6 (33개 포탄)으로 이동하고,

파란 함선은 1 2 5 4 6 (53개 포탄)으로 이동한다.

두 경로에서 출발과 도착을 제외하면 중복되는 정점과 간선이 없으므로 조건을 만족하면서 

두 함선이 발사한 포탄의 합은 86개로 가장 적은 개수이다.




입력의 첫째 줄에는 중간 지점의 수 v와 뱃길의 수 e가 주어진다. (3 ≤ v ≤ 1000, 3 ≤ e ≤ 10000) 
다음 e개 줄에는 뱃길의 정보 ai, bi, ci가 주어진다. (1 ≤ ai, bi ≤ v, ai ≠ bi, 1 ≤ ci ≤ 100) 
ai는 뱃길의 시작 지점, bi는 도착 지점, ci는 그 뱃길로 이동할 때 발사해야 하는 포탄의 수이다.

전술의 시작 지점은 1이고, 목적지는 v이다. 
항상 1과 v사이에 겹치지 않는 경로가 적어도 두 개 있다.



전술을 따르면서 두 전함이 발사해야 하는 포탄의 최소 개수를 출력한다.


6 11
1 2 23
1 3 12
1 4 99
2 5 17
2 6 73
3 5 3
3 6 21
4 6 8
5 2 33
5 4 5
6 5 20
86





MCMF

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.