ダイクストラのアルゴリズム

マジ意味不

　わからないなりに螺旋本を見つつ、アルゴリズムをpythonのコード化し、この問題に適用してみた

n,k = map(int,input().split())
inf=10**10
e = [[inf]*n for _ in range(n)]

def dijkstra(s,g):
    color=["WHITE"]*n
    d=[inf]*n
    p=[-1]*n
    d[s]=0
    p[s]=-1
    while True:
        mincost =inf
        for i in range(n):
            if color[i] !="BLACK" and d[i] < mincost:
                mincost =d[i]
                u=i
        if mincost ==inf:
            break
        color[u]="BLACK"
        
        for v in range(n):
            if color[v] !="BLACK" and e[u][v] !=inf:
                if d[u] +e[u][v] <d[v]:
                    d[v]=d[u] +e[u][v]
                    p[v]=u
                    color[v] ="GRAY"
    return d[g]

for i in range(k):
    S=list(map(int,input().split()))
    if S[0]==1:
        a,b,c=S[1],S[2],S[3]
        a-=1
        b-=1
        if e[a][b]>c:
            e[a][b]=c
            e[b][a]=c
    else:
        a,b=S[1],S[2]
        a-=1
        b-=1
        ret=dijkstra(a,b)
        if ret==inf:
            print(-1)
        else:
            print(ret)

優先度つきキューは使用していないためダメかと思ったがなんとか行けた。
BFSとかDFSで初めて解けた以来の感動がある。