[アルゴリズム]未来都市

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]を設定します.