JOI 2007 予選 F 船旅 - いろんなことで四苦Hack（仮）

続きです。

これはすげー簡単だった。まぁ100点問題だしね。

コピペで瞬殺！！！

import queue
push = queue.heappush
pop = queue.heappop
INF = 10**16

def dijkstra(s, G, d):
    q = []
    d[s] = 0
    push(q, (0, s))

    while q:
        cost, v = pop(q)
        # print(f'd[{v}] = {cost}')
        # 既に q から取り出したものの方が低い
        if d[v] < cost:
            continue
        for to, tmpcost in G[v]:
            if d[to] > d[v] + tmpcost:
                d[to] = d[v] + tmpcost
                push(q, (d[to], to))

from collections import defaultdict

G = defaultdict(list)
N, K = map(int, input().split())

d = [INF]*N

for i in range(K):
    line = list(map(int, input().split()))
    if line[0] == 0:
        dijkstra(line[1]-1, G, d)
        if d[line[2]-1] == INF:
            print(-1)
        else:
            print(d[line[2]-1])
        d = [INF]*N
    else:
        G[line[1]-1].append((line[2]-1, line[3]))
        G[line[2]-1].append((line[1]-1, line[3]))

単純な最短路問題。前回よりもっとシンプルだった。