[アルゴリズム]未来都市
7924 ワード
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 방향 제외
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 양방향
for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
x, k = map(int, input().split())
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print("-1")
else:
print(distance)
1番ノードから5番ノードから4番ノードまでの問題.
問題のみを見れば複数の問題を自由に解くことができるが,時間的に複雑度が高いため,より実現しやすいfloydwalshアルゴリズムを用いて実現した.
距離図を作成する際には自分と1-2(1->2->1)が双方向に移動できることを考慮して距離図を作成した.
開始ノード、ターゲットノード、中間ノードを含む3 Dドアを作成します.
distanceは中間ノードを通過しなければならないからです.
distance=graph[1][k]+graph[k][x]を設定します.
Reference
この問題について([アルゴリズム]未来都市), 我々は、より多くの情報をここで見つけました https://velog.io/@jifrozen/Algorithm-미래도시テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol