Informatica Online Judge

  경곽이와 하트 [0998 / 03E6]

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


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

[koistudy.net (T. HJ Jeong)]

Background

경곽, 서곽, 종곽이 3명이 있다. 경곽이는 서곽이에게 게임을 위한 하트를 10개 주기로 약속을 하였다. 또한, 서곽이는 종곽이에게 하트 10개를 주어야 한다. 이 3명이 서로에게 주고 받아야 하는 하트를 정리하려고 한다.

경곽 -> 서곽 (10개)
서곽 -> 종곽 (10개)

따라서 총 하트의 개수는 20개가 필요하다.

하지만 경곽이가 종곽이에게 직접 10개를 주면 모든 하트의 주고 받는 결과는 동일하며 단, 하트의 이동은 10개가 된다.

경곽 -> 종곽 (10개)

10개 이하로 모든 하트를 정리할 방법은 없다. 모든 하트의 주고 받는 것을 결정하는데 필요한 최소 하트의 이동값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 총 사람의 수 n과 서로 하트를 주고 받는 관계의 수를 나타내는 m이 공백으로 구분되어 입력된다.

두 번째 줄부터 m 줄에 걸쳐서 하트의 주어야할 사람의 번호, 하트를 받아야 하는 사람의 번호, 주어야 할 하트의 갯수 C가 공백으로 구분되어 입력된다.

[입력값의 정의역]
2 <= n <= 100
1 <= m <= 10,000
1 <= C <= 100

Output

최소 이동 갯수를 출력한다.

IO Example

입력
3 2
1 2 10
2 3 10

출력
10

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