Informatica Online Judge

  과제제출 [0956 / 03BC]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 55   Total Tried : 80


The Champion of this Problem (C++) : gs15120 - 0ms / 1323byte
My Best Submission (C++) : N/A

[Jihak Yoon (koistudy.net)]

Background

경곽이는 학교의 수많은 숙제들을 제출해야 한다.

보통은 이 숙제들을 수업 시간 중에 걷거나 방과 후에 걷지만, 오늘은 왠지 재수가 좋지 않았다. 경곽이는 쉬는 시간 10분 동안 수많은 숙제들을 전부 내야 되는 것이다!

그런데 경곽이의 학교는 슬프게도 건물이 매우 많고 이들 사이의 거리 또한 상당하다고 한다.

어쩔 수 없이 경곽이는 열심히 달려 모든 숙제들을 내기로 했다.

그러나 너무 빨리 달리면 숨이 차서 다음 수업을 듣는 데 지장이 생길 수 있고, 너무 천천히 달리면 쉬는 시간 안에 모든 숙제를 다 제출하지 못할 수도 있다.

그래서 경곽이는 당신에게 자신이 이동해야 하는 최소 거리가 어느 정도 되는지를 구해 달라고 부탁했다.

경곽이는 당신에게 자신이 이동할 때 지키는 몇 가지 규칙을 알려 주었다.

1. 경곽이는 처음에 1번 건물에서 출발하여 마지막에 N번 건물에 도착해야 한다.
2. 경곽이는 모든 건물을 정확히 한 번만 방문해야 한다. 1번 건물은 맨 처음에 방문한 것으로 친다.

위 규칙들을 모두 만족시키는 최소 이동 거리를 구하여라.

Input

첫 줄에 건물의 수 N이 주어진다. ( 1<=N<=10 )
다음 N줄에 N개의 수 A(i,j)가 공백을 사이에 두고 주어진다. 이 수는 건물 i와 건물 j 사이의 거리를 의미한다.
또한 A(i,i)=0이고, A(i,j)=A(j,i)이다. ( 1<=A(i,j)<=100,000,000 )

Output

문제에서 요구한 답을 한 줄에 출력한다.

IO Example

입력1

2
0 1
1 0

출력1

1

입력2

5
0 1 2 3 4
1 0 2 3 4
2 2 0 3 4
3 3 3 0 4
4 4 4 4 0

출력2

10

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