Problem p02726 (python)

Fixed submission:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N,X,Y=map(int,input().split())
    V, E= N,N
    g = [[] for i in range(V)]

    for i in range(N-1):
        g[i].append((1, i+1))
        g[i+1].append((1, i))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
    g[X-1].append((1, Y-1))
    g[Y-1].append((1, X-1))

    INF = 10 ** 10
    ans = [0] * N

    for r in range(N):
        for i in dijkstra(V, g, r):
            if i<INF:
                ans[i]+=1

    for j in range(1, N):
        print(ans[j] // 2)


resolve()

Buggy submission (verdict: Runtime Error):
def resolve():
    # 最短経路問題で使われるアルゴリズムの１つ。
    # グラフ上の全ての頂点間の最短経路を探す
    # 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

    # 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
    # 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
    def warshall_floyd(v_num, e_num, dist_lst):

        # 負の閉路を持つか

        # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
        # よりコストの合計が小さい方を配列に入れる動的計画法
        for k in range(v_num):
            for i in range(v_num):
                for j in range(v_num):
                    # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                    if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                        if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                            dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

        ans=[0]*N
        for lst in dist_lst:
            for i in range(len(lst)):
                ans[lst[i]]+=1

        for j in range(1,N):
            print(int(ans[j]))

    N,X,Y=map(int,input().split())
    # 頂点の数と辺の数
    v_num, e_num = N,N

    # 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
    # a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
    INF = 10 ** 20
    dist_lst = [[INF] * v_num for _ in range(v_num)]

    for i in range(v_num-1):
        dist_lst[i][i+1] = 1
    dist_lst[X-1][Y-1] = 1


    for v in range(v_num):
        dist_lst[v][v] = 0

    warshall_floyd(v_num, e_num, dist_lst)





resolve()

Buggy submission (verdict: Runtime Error):
def resolve():
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    N,X,Y=map(int,input().split())
    # 距離行列の生成
    dist_matrix = [[0] * (N) for _ in range(N)]
    for i in range(N):
        dist_matrix[i][i] = 0
    for i in range(N-1):
        dist_matrix[i][i+1] = 1
        dist_matrix[i+1][i]=1
    dist_matrix[X-1][Y-1] = 1
    dist_matrix[Y-1][X-1] = 1


    graph = csr_matrix(dist_matrix)
    # ワーシャルフロイド
    dist_matrix = floyd_warshall(csgraph=graph, directed=False)
    ans = [0] * N
    for lst in dist_matrix:
        for i in range(len(lst)):
            ans[int(lst[i])] += 1

    for j in range(1, N):
        print(ans[j] // 2)






resolve()