Informatica Online Judge

  대도시 만들기 [2119 / 0847]

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


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

[koistudy.net (unkonwn)]
Writer ID : [gs16044]

Background

대한민국에는 도시가 N개 있다. 이 중 인구수가 적은 시골 도시는 1번 도시부터 R번 도시까지 R 개다. 대한민국의 수도 서울은 항상 R+1 번 도시이다.

정부는 도시 a 와 도시 b 사이의 “교통비”를 도시 a에서 서울을 거쳐 도시 b 로 가는 최단 거리로 정의하였다.
정부는 R 개의 시골 도시 중 K 개를 선택하여 대도시를 만들고자 한다.
K 개의 도시들을 각각 C(1) C(2) .... C(K) 라고 하자.
이 때 대도시의 “크기”를 임의의 두 도시 C(i) 와 C(j) 를 잡았을 때
C(i) 와 C(j) 사이의 “교통비”의 총 합으로 정의한다.

예를 들어 세 도시 A B C 가 대도시로 선택되었다고 하자.
이 때 대도시의 “크기”는 A와 B 사이, B와 A 사이, B 와 C 사이, C와 B사이, A와 C 사이, C 와 A 사이의 “교통비”의 합이다.

정부는 K 개의 도시로 이루어진 대도시의 “크기”를 가능한 크게 하고자 한다.
이 때 대도시의 “크기”를 출력하면 된다.

임의의 두 정점 사이를 항상 갈 수 있음이 보장된다.

Input

첫 줄에 N, R, K, M(간선 개수)이 순서대로 입력된다. ( 2 <= R < N <= 5000 , 간선은 단방향, M <= 50000, 2 <= K <= R)

두 번째 줄부터 M+1 번째 줄까지에는 세 수 S, E, C 가 입력된다.

S는 시작점이고 E는 도착점이며 C는 거리다. (S와 E는 N 이하, C는 0 이상 10000 이하)

Output

첫 줄에 대도시의 최대 “크기”를 출력한다.

IO Example

입력
9 6 3 11
1 2 1
2 3 2
3 4 3
4 6 4
6 8 5
8 9 6
9 7 7
7 5 8
5 8 8
7 6 9
6 1 10

출력
282

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