| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 436588 | Lam_lai_cuoc_doi | 여행하는 상인 (APIO17_merchant) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
N = int(1e11)
w = [[N * N for i in range(102)] for i in range(102)]
d = [[0 for i in range(102)] for i in range(102)]
b = [[0 for i in range(1002)] for i in range(102)]
s = [[0 for i in range(1002)] for i in range(102)]
def Floyd(n, k):
for k in range(1, n + 1):
for u in range(1, n + 1):
for v in range(1, n + 1):
w[u][v] = min(w[u][v], w[u][k] + w[k][v])
for u in range(1, n + 1):
for v in range(1, n + 1):
for i in range(1, k + 1):
if s[v][i] != -1 and b[u][i] != -1:
d[u][v] = max(d[u][v], s[v][i] - b[u][i])
def Check(n, v):
dp = [[N * N for i in range(102)] for i in range(102)]
for i in range(1, n + 1):
for j in range(1, n + 1):
dp[i][j] = w[i][j] * v - d[i][j]
for k in range(1, n + 1):
for u in range(1, n + 1):
for v in range(1, n + 1):
dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v])
for u in range(1, n + 1):
for v in range(1, n + 1):
if u != v and dp[u][v] + dp[v][u] <= 0:
return True
return False
n, m, k = map(int, input().split())
for i in range(1, n + 1):
w[i][i] = 0
a = list(map(int, input().split()))
t = 0
for j in range(1, k + 1):
b[i][j] = a[t]
s[i][j] = a[t + 1]
t = t + 2
for i in range(0, m):
u, v, c = map(int, input().split())
w[u][v] = c
Floyd(n, k)
l = -N
r = N
while l <= r:
mid = (l + r) // 2
if Check(n, mid):
l = mid + 1
else:
r = mid - 1
print(r)