Submission #921861

#	Time	Username	Problem	Language	Result	Execution time	Memory
921861		vjudge1	Travelling Merchant (APIO17_merchant)	Cpython 3	0 / 100	47 ms	9300 KiB

merchant

def bellman_ford(n, m, k, markets, footpaths):
    INF = float('inf')
    
    dist = [0] + [-INF] * n  # Initialize distances with -INF
    
    for _ in range(n - 1):  # Run Bellman-Ford algorithm
        for u, v, w in footpaths:
            if dist[u] != -INF and dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    
    max_efficiency = 0
    
    for _ in range(n):  # Iterate for each market as a starting point
        for u, v, w in footpaths:
            if dist[u] != -INF and dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                max_efficiency = max(max_efficiency, dist[v] // k)
    
    return max_efficiency

# Input processing
n, m, k = map(int, input().split())
markets = [list(map(int, input().split())) for _ in range(n)]
footpaths = [tuple(map(int, input().split())) for _ in range(m)]

# Solve and print the result
result = bellman_ford(n, m, k, markets, footpaths)
print(result)

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