atcoder ABC208＿D pythonでTLEになってしまう

Question

前提・実現したいこと

表題についてpythonで下記の問題のコードを提出したところ、TLEになってしまいました。
ABC208_D問題

原因は分かっており、コード内の下記の記載を変更したところACになりました。
（誤）float('inf')　⇒（正）INF　←INF=10**18　を設定
ここで質問なのですが、そもそも（誤）のパターンは何が問題だったのでしょうか？
（感覚的にはWAならまだ分かるのですが、、）

どなたかご教授頂けますと幸いです。

発生している問題・エラーメッセージ

10個のパターンでTLEになっています。

該当のソースコード

N,M = map(int,input().split())
G = [[float('inf') for _ in range(N)] for _ in range(N)]

for i in range(N):
    G[i][i] = 0

for i in range(M):
    A,B,C = map(int,input().split())
    G[A-1][B-1] = C

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j],G[i][k]+G[k][j])
            if G[i][j] != float('inf'):
                ans += G[i][j]
print(ans)

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください

Answer 1

遅くなる以下の部分です。

G = [[float('inf') for _ in range(N)] for _ in range(N)]

float(inf)をN**2回実行します。以下の方が速いでしょう。

G = [[float('inf')] * N] * N

次に、

            G[i][j] = min(G[i][j],G[i][k]+G[k][j])

では、G[i][j] がintでG[i][k]+G[k][j]がinfの場合にintからfloatへの型変換が発生します。

            if G[i][j] != float('inf'):

ここが一番遅くなる原因です。
まず、float(inf)がN**3回実行されます。さらにG[i][j] がintの場合にintからfloatへの型変換が発生します。

Comments

[pawapoke]

確かに至る所で型変換が必要になるパターンがありますね。。
（正）のコードで上手くいったのはint型で定義してたからなのですね。
型変換自体がそこまで計算量に影響を与えるという認識もありませんでした。
大変勉強になりました。

ppaulさん、ご回答ありがとうございます。