Graph/Weighted_Digraph/Warshall_Floyd.py

• View this file on GitHub
• Last update: 2024-02-25 11:56:41+09:00

Code

from Weighted_Digraph import *

def Warshall_Floyd(D: Weigthed_Digraph):
    """ Warshall-Floyd 法を用いて, 全点間距離を求める.

    D: 重み付き有向グラフ
    """

    N = D.order()
    inf = float('inf')

    dist = [[0 if u == v else inf for v in range(N)] for u in range(N)]

    def three_loop():
        for r in range(N):
            dist_r = dist[r]
            for p in range(N):
                dist_p = dist[p]
                for q in range(N):
                    dist_p[q] = min(dist_p[q], dist_p[r] + dist_r[q])

    for u in range(N):
        dist_u = dist[u]
        for v, w, _ in D.adjacent_out[u]:
            dist_u[v] = min(dist_u[v], w)

    three_loop()

    if any(dist[u][u] < 0 for u in range(N)):
        for u in [u for u in range(N) if dist[u][u] < 0]:
            dist[u][u] = -inf
        three_loop()

    return dist

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page