練習問題/解答例/クリティカルパス/Python
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[問題文>練習問題#o006da2d]]
def dijk(s):
global d, prev
d = [0] * V
used = [False] * V
prev = [-1] * V
d[s] = 0
while 1:
v = -1
for u in xrange(V):
if v!=-1 and cost[v][u] == INF: continue
if not used[u] and (v==-1 or d[u] > d[v]): v = u
if v == -1: break
used[v] = True
for u in xrange(V):
if cost[v][u] == INF: continue
if d[u] < d[v] + cost[v][u]:
d[u] = d[v] + cost[v][u]
prev[u] = v
def get_path(t):
path = []
while t != -1:
path.append(chr(ord('A')+t))
t = prev[t]
return ' -> '.join(path[::-1])
V, E = map(int, raw_input().split())
INF = 987654321
cost = [ [ INF for _ in xrange(V+1) ] for _ in xrange(V+...
for _ in xrange(E):
a, b, c = raw_input().split()
a = ord(a) - ord('A')
b = ord(b) - ord('A')
cost[a][b] = int(c)
dijk(0)
print get_path(V-1)
print d[V-1]
終了行:
[[問題文>練習問題#o006da2d]]
def dijk(s):
global d, prev
d = [0] * V
used = [False] * V
prev = [-1] * V
d[s] = 0
while 1:
v = -1
for u in xrange(V):
if v!=-1 and cost[v][u] == INF: continue
if not used[u] and (v==-1 or d[u] > d[v]): v = u
if v == -1: break
used[v] = True
for u in xrange(V):
if cost[v][u] == INF: continue
if d[u] < d[v] + cost[v][u]:
d[u] = d[v] + cost[v][u]
prev[u] = v
def get_path(t):
path = []
while t != -1:
path.append(chr(ord('A')+t))
t = prev[t]
return ' -> '.join(path[::-1])
V, E = map(int, raw_input().split())
INF = 987654321
cost = [ [ INF for _ in xrange(V+1) ] for _ in xrange(V+...
for _ in xrange(E):
a, b, c = raw_input().split()
a = ord(a) - ord('A')
b = ord(b) - ord('A')
cost[a][b] = int(c)
dijk(0)
print get_path(V-1)
print d[V-1]
ページ名:
