백준2141(우체국) - pypy해결

우체국

 

문제

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

 

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

 

출력

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

---

처음에는 dfs로 하려고하였는데 뭔가 안된다. 이유는 모르겠다.

그래서 보니 플로이드-와샬문제였다.

그래서 플로이드-와샬로 하고 행렬에서 i행, i열의 원소는 자기 자신에서 자기 자신으로 오는 최소 거리가 되기때문에

거기중 가장 작은 값아 답이된다. 없다면 -1

하지만 python으로는 안된다.

import sys
input = sys.stdin.readline

V, E = map(int,input().split())
INF = 987654321
D = [[INF] * V for _ in range(V)]

for _ in range(E):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    D[a][b] = c
# 플로이드-와샬
for k in range(V):
    for j in range(V):
        for i in range(V):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]

# 최소값찾기
min_D = INF
for i in range(V):
    if min_D > D[i][i]:
        min_D = D[i][i]
# 최소값이 없다면 -1
if min_D == INF:
    print(-1)
else:
    print(min_D)