당신은 N개의 섬으로 구성된 한 공원을 방문하고 있다.

모든 섬에는 어느 섬으로든 이어진 다리가 정확하게 하나씩 있다.

i째 섬에서 외부로 나가는 다리의 길이를 Li라고 하자.

따라서 공원에는 N개의 다리가 존재하는 셈이다.

물론 다리는 양방향으로 모두 통행 가능하다.

그에 덧붙여 페리도 왕복 운행을 하고 있기 때문에 아무 섬에서 아무 섬으로나 원하는 대로 이용할 수 있다.

하지만 당신은 페리를 타는 것보다 걷는 것을 더 좋아한다.

그렇기 때문에 공원을 순회하면서 다리를 따라 걷는 거리를 최대화하되, 아래의 조건을 만족하고 싶어한다.

● 순회의 시작은 당신이 원하는 아무 섬에서나 하면 된다. ● 들른 적이 있는 섬을 또 거쳐서는 안 된다. ● 당신이 S라는 섬에 있고 예전에 들른 적이 없는 D라는 섬이 있다면, S에서 D까지는 아래의 둘 중 한 방법으로 아무 때에나 이동 가능하다.

― 도보: 두 섬이 다리로 연결되어 있어야만 이 방법이 가능하다.

다리를 이용하면 당신이 걸은 전체 거리에 다리의 길이가 더해진다. ― 페리: S에서 D까지 기존 다리와 예전에 이용한 적이 있는 페리 운항 경로를 조합해서는 도달할 수 없을 때만 이용 가능하다.

(섬과 섬 사이의 도달 가능성을 판별할 때는, 내가 이미 도달한 적이 있어서 더는 되돌아갈 수 없는 섬을 통과하는 경로까지 모두 감안해야 한다.)

모든 섬들을 하나도 빠짐없이 들러야 할 필요는 없다.

또한 공원에 존재하는 다리를 전부 거치는 것이 불가능할 수도 있다.

N개의 다리의 위상 정보와 길이를 입력 받아,

위의 규칙대로 공원을 순회하면서 다리들을 이용해 걸을 수 있는 가장 긴 거리를 구하는 프로그램을 작성하시오.

[예제 설명]

예제로 제시되어 있는 N=7 공원은 아래 그림과 같이

(1-3), (2-7), (3-4), (4-1), (5-1), (6-3), (7-2)와 같은 형태로 섬들이 다리로 연결되어 있다.

2번 섬과 7번 섬은 다리가 두 개 존재함을 주목하기 바란다.

도보 경로를 가장 길게 확보하려면 섬을 다음과 같이 순회하면 된다.

5번 섬에서 출발한다.

길이가 9인 다리를 이용해 1번 섬으로 간다.

길이가 8인 다리를 이용해 3번 섬으로 간다.

길이가 4인 다리를 이용해 6번 섬으로 간다.

6번 섬에서 7번 섬까지는 페리를 이용한다.

길이가 3인 다리를 이용해 2번 섬으로 간다.

순회는 2번 섬에서 끝나며 이때 당신이 걸은 총 거리는 9+8+4+3=24이다.

한 번도 들르지 않은 유일한 섬은 4번 섬이다. 하지만 이제는 거기에 갈 수 없다.

왜냐 하면 2번 섬과 4번 섬은 직통으로 연결하는 다리가 없이 고립되어 있어서 일단 도보로 갈 수 없으며,

위의 규칙대로라면 페리도 이용할 수 없기 때문이다.

이미 페리를 이용한 구간인 (6-7)까지 감안하면 2번 섬과 4번 섬은 이제 연결된 것으로 간주되기 때문이다.

(다리 2-7, 이미 이용한 페리 7-6, 다리 6-3, 다리 3-4로 연결)

페리는 그런 방법으로 도달할 수 없는 완전히 새로운 곳으로만 이용할 수 있다.

섬순회(Islands) timer 2s memory 128MB

섬순회(Islands) 2s 128MB