Submission #436587

#	Time	Username	Problem	Language	Result	Execution time	Memory
436587		Lam_lai_cuoc_doi	Travelling Merchant (APIO17_merchant)	Cpython 3	0 / 100	1095 ms	9452 KiB

merchant

N = int(1e20)
w = [[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)

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34