Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
PyCPXで最短路問題を解く
# -*- coding: utf-8 -*-
import numpy as np
from pycpx import CPlexModel
# 入力(有向グラフ,頂点は0-index)
# n m
# s_1 t_1 c_1
# s_2 t_2 c_2
# ...
# s_m t_m c_m
n, m = map(int, raw_input().split())
model = CPlexModel()
d = model.new(n)
model.constrain(d[0] == 0)
for i in range(m):
s, t, c = map(int, raw_input().split())
model.constrain(d[t] <= d[s] + c)
model.maximize(d[n-1])
print model[d]
# 4 5
# 0 1 1
# 0 2 4
# 1 2 2
# 2 3 1
# 1 3 5
# -> [ 0. 1. 3. 4.]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment