# BOJ - 9870 - Vacation Planning

Updated:

```
import sys
INF = 1e9
MAX = 201
def solution():
cnt, sum = 0, 0
N, M ,K, Q = map(int, sys.stdin.readline().split())
matrix = [[INF for _ in range(MAX)] for _ in range(MAX)]
for _ in range(M):
U, V, D = map(int, sys.stdin.readline().split())
matrix[U][V] = D
for i in range(MAX):
for j in range(MAX):
if i == j: matrix[i][j] = 0
for k in range(N+1):
for i in range(N+1):
for j in range(N+1):
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
for i in range(Q):
U, V = map(int, sys.stdin.readline().split())
cost = INF
for j in range(K+1):
cost = min(cost, matrix[U][j] + matrix[j][V])
if cost != INF:
cnt += 1
sum += cost
print(cnt)
print(sum)
solution()
```

https://www.acmicpc.net/problem/9870

## Leave a comment