Submission #63854618

---

Source Code Expand

import sys
import pulp
def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    edges = []
    index = 3
    for j in range(M):
        u = int(data[index])
        v = int(data[index + 1])
        index += 2
        edges.append((u, v))
    prob = pulp.LpProblem("MaximizeShortestDistance", pulp.LpMaximize)
    y = [pulp.LpVariable(f"y_{j}", cat=pulp.LpBinary) for j in range(M)]
    d = [None] + [pulp.LpVariable(f"d_{i}", lowBound=0, cat=pulp.LpContinuous) for i in range(1, N+1)]
    prob += (d[1] == 0)
    for j, (u, v) in enumerate(edges):
        prob += (d[v] <= d[u] + y[j])
    prob += (pulp.lpSum(y) == K)
    prob += d[N]
    solver = pulp.PULP_CBC_CMD(msg=False)
    prob.solve(solver)
    result = int(pulp.value(d[N]))
    print(result)
if __name__ == '__main__':
    main()

Submission Info

Judge Result