Informatica Online Judge

  배달 알바 [2134 / 0856]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 8   Total Tried : 9


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 박준호]
Writer ID : [gs16042]

Background

호준이는 경곽 마을에서 가장 잘 나가는 음식점인 레스토랑스에서 음식을 배달하는 알바를 시작했다. 어느 날 호준이는 배달 주문이 밀려 한꺼번에 배달을 처리하려고 한다.

하지만 호준이는 음식 3개를 들자 팔이 호들호들거리는 것을 느꼈다. 그래서 그는 한번 배달할 때마다 두 개의 집에 배달을 하기로 하였다.

호준이는 시간을 가장 적게 들여서 모든 집에 배달을 하고 싶다. 단, 두 개의 음식을 모두 배달하기 전까지는 새로운 음식을 다시 가게에서 가져가지 않는다고 하자. 또한, 호준이는 모든 배달을 마친 후 다시 가게로 돌아와야 한다.

레스토랑스의 위치는 0이다.

Input

맨 첫 줄에 배달할 집의 개수 n (n<=10, n은 짝수) 과 도로의 개수 m (n-1<=m<=) 이 입력된다.
그 후 m줄에 거쳐 각 줄마다 연결 지점과 길이가 주어진다. 단, 연결이 안 되어있는 집은 없다.

Output

호준이가 모든 집에 배달을 완료하고 가게로 돌아왔을 때 이동하는 최단 거리를 출력한다.

IO Example

입력 예시
6 8
0 1 4
0 2 6
1 2 5
2 4 5
3 5 7
2 5 3
1 3 4
5 6 2

출력 예시
60

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]