Problem:


船旅  

問題

JOI国には，n 島の島があり，各島には 1 から n までの番号が付けられている．現在，JOI国では各島の間を結ぶ航路網の整備が進んでいる．

あなたは，船舶の切符を扱っているチケットセンターに勤務している．JOI国には船舶を使って，できる限り安価に，島と島の間を旅行したいと考えている人が沢山おり，彼らは，出発地と目的地を注文票に記入して，あなたのところに送ってくる．

あなたの仕事は，客から注文票を受け取ったらすぐに，いくつかの船舶を乗り継いで，出発地と目的地を結ぶ航路の中で，もっとも安価な運賃を計算し，客に伝えることである．
ただし，旅程によっては，船舶を使って旅行することが出来ない場合もある．そのときは『船舶を使って旅行することが出来ない』と客に伝える必要がある．また，JOI国では，島と島の間を結ぶ新しい船舶が，次々と運航を開始しており，あなたには，その情報が随時伝えられる．客に返事をする際には，最新の情報に留意しなければならない．

入力として，客の注文票や新たに運航を開始した船舶の運航情報が与えられたときに，客への返事を求めるプログラムを作成せよ．

なお，入力例１と出力例１に対する実行状況を，図１として図示している．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力の 1 行目には2つの整数 n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 5000) が書かれている．これは，島の数が n 島で，入力が k + 1 行からなることを表す．
i + 1 行目 (1 ≤ i ≤ k) には， 3 個または 4 個の整数が空白を区切りとして書かれている．

    
 最初の数字が 0 のとき，この行は客の注文票を表す．

      この行には3個の整数 0, a, b (1 ≤ a ≤ n, 1 ≤ b ≤ n, a &ne; b) が空白を区切りとして書かれている．
      これは，客が，島 a を出発地とし島 b を目的地とするような注文票を送ってきたことを表す．

    
 最初の数字が 1 のとき，この行は新たに運航を開始した船舶の運航情報を表す．

      この行には 4 個の整数 1, c, d, e (1 ≤ c ≤ n, 1 ≤ d ≤ n, c &ne; d, 1 ≤ e ≤ 1000000) が書かれている．

      これは島 c と島 d を往復する船舶が新たに運航を開始し，この船舶の島 c から島 d への運賃と，島 d から島 c への運賃が，共に e であることを表す．

      この行以降の注文票に対しては，この船舶も考慮して返事をしなければならない．

最初の段階では，船舶は一隻も運航していないものとする．入力のうち，船舶の運航情報を表す行は 1000 行以下である．また，島と島の間に，複数の船舶が運航することがあることに注意せよ． 

n, k がともに 0 のとき入力の終了を示す. データセットの数は 5 を超えない．

出力

データセットごとに以下の形式で出力する．

入力のうち，注文票を表す行の数を m とおく．
 各データセットの出力は m 行からなり， i 行目(1 ≤ i ≤ m)には， i 番目の注文票に対する返事を表す整数を書く．
すなわち， i 番目の注文票の出発地と目的地の間を，いくつかの船舶を乗り継いで旅行することが可能ならば，その運賃の合計の最小値を書く．旅行することが不可能ならば，-1 を出力する．

入出力例

入力例

3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3
5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3
0 0

出力例

-1
15
12
5955
21431
9298
16392
24774
8840

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3
5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3
0 0


Sample output:
-1
15
12
5955
21431
9298
16392
24774
8840

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    U[v] = 1
    if v == g:
      break
    for e in E[v]:
      if not U[e[0]] and D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    if v == g:
      break
    for e in E[v]:
      if D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        ans = D[lst[1] - 1][lst[2] - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(n):
            D[i][j] = min(D[i][j], D[i][a - 1] + c + D[b - 1][j], D[i][b - 1] + c + D[a - 1][j])
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(j + 1)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        ans = D[b - 1][a - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(i):
            D[i][j] = min(D[i][j],
            D[max(i, a - 1)][min(i, a - 1)] + c + D[max(j, b - 1)][min(j, b - 1)],
            D[max(i, b - 1)][min(i, b - 1)] + c + D[max(j, a - 1)][min(j, a - 1)])
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        ans = D[lst[1] - 1][lst[2] - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(i):
            D[i][j] = min(D[i][j],
                          D[i][a - 1] + c + D[b - 1][j],
                          D[i][b - 1] + c + D[a - 1][j])
            D[j][i] = D[i][j]
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
def solve():
    max_fare = 99000001
    def dijkstra(start, goal):
        unvisited = [i for i in range(n)]
        fare = [max_fare] * n
        fare[start] = 0
        
        while True:
            min_fare = max_fare
            for i in unvisited:
                f = fare[i]
                if f < min_fare:
                    min_fare = f
                    u = i
                    
            if u == goal:
                return min_fare
            elif min_fare == max_fare:
                return -1
            
            unvisited.remove(u)
            
            for v, f in enumerate(adj_matrix[u]):
                if v in unvisited:
                    fare[v] = min(min_fare + f, fare[v])
        
    import sys
    file_input = sys.stdin

    while True:
        n, k = map(int, file_input.readline().split())
        if n == 0 and k == 0:
            break
        
        adj_matrix = [[max_fare] * n for i in range(n)]
        
        for i in range(k):
            line = file_input.readline()
            if line[0] == '0':
                a, b = map(int, line[2:].split())
                print(dijkstra(a - 1, b - 1))
            else:
                c, d, e = map(int, line[2:].split())
                f = min(adj_matrix[c - 1][d - 1], e)
                adj_matrix[c - 1][d - 1] = f
                adj_matrix[d - 1][c - 1] = f

solve()

Submission status: Time Limit Exceeded

Solution code:
while 1:
    INF = 10**9
    N, K = map(int, input().split())
    if N == K == 0:
        break
    E = [[INF]*N for i in range(N)]
    for i in range(N):
        E[i][i] = 0
    ans = []
    for i in range(K):
        q, *c = map(int, input().split())
        if q == 0:
            a, b = c
            cost = E[a-1][b-1]
            if INF <= cost:
                ans.append(-1)
            else:
                ans.append(cost)
        else:
            c, d, e = c
            if e < E[c-1][d-1]:
                E[c-1][d-1] = E[d-1][c-1] = e
                for i in range(N):
                    for j in range(N):
                        E[i][j] = E[j][i] = min(E[i][j], E[i][c-1] + e + E[d-1][j], E[i][d-1] + e + E[c-1][j])
    print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def floyd(n,L):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                L[i][j]=min(L[i][j],L[i][k]+L[k][j])

while True:
    n,k=map(int,raw_input().split())
    if n==k==0:break
    INF=1e10
    L=[[INF]*n for i in range(n)]
    for i in range(n):
        L[i][i]=0
    for i in range(k):
        order=map(int,raw_input().split())
        if order[0]==1:
            c,d,e=order[1:]
            c-=1
            d-=1
            L[c][d]=L[d][c]=e
            floyd(n,L)
        else:
            a,b=order[1:]
            a-=1
            b-=1
            print L[a][b] if L[a][b]!=INF else -1

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        fare, node = heappop(heap)
        if node == t:
            return fare
        if node in visited:
            continue
        for fare2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (fare + fare2, node2))
    return -1


while True:
    n, k = map(int, input().split())
    if not n:
        break
    links = [set() for _ in range(n)]
    for _ in range(k):
        o = map(int, input().split())
        if next(o):
            c, d, e = o
            c, d = c - 1, d - 1
            links[c].add((e, d))
            links[d].add((e, c))
        else:
            a, b = o
            print(dijkstra(a - 1, b - 1, links))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        fare, node = heappop(heap)
        if node == t:
            return fare
        if node in visited:
            continue
        visited.add(node)
        for fare2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (fare + fare2, node2))
    return -1


while True:
    n, k = map(int, input().split())
    if not n:
        break
    links = [set() for _ in range(n)]
    for _ in range(k):
        o = map(int, input().split())
        if next(o):
            c, d, e = o
            c, d = c - 1, d - 1
            links[c].add((e, d))
            links[d].add((e, c))
        else:
            a, b = o
            print(dijkstra(a - 1, b - 1, links))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
TLE
"""
import sys
from sys import stdin
from heapq import heappush, heappop
from collections import namedtuple
input = stdin.readline


def warshall_floyd(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                new_cost = d[i][k] + d[k][j]
                if new_cost < d[i][j]:
                    d[i][j] = new_cost


def main1(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break

        d = [[float('inf')] * (n+1) for _ in range(n+1)]
        #for i in range(n+1):
        #    d[i][i] = 0

        updated = False
        for _ in range(k):
            data = [int(x) for x in input().split()]
            if data[0] == 0:
                if updated:
                    warshall_floyd(d, n+1)
                    updated = False
                f, t = data[1], data[2]
                if d[f][t] == float('inf'):
                    print(-1)
                else:
                    print(d[f][t])
            else:
                f, t, c = data[1], data[2], data[3]
                if c < d[f][t]:
                    d[f][t] = c
                    updated = True
                if c < d[t][f]:
                    d[t][f] = c
                    updated = True


edge = namedtuple('edge', ['t', 'c'])
def dijkstra(s, G):
    pq = []
    d = [float('inf')] * len(G)
    d[s] = 0
    heappush(pq, (0, s))

    while pq:
        c, v = heappop(pq)
        if d[v] < c:
            continue

        for e in G[v]:          #  ?????????v?????£??\??????????????±????????¨?????????????????°?????§?????????????????´??°
            if d[e.t] > d[v] + e.c: #  ???????????§??\??£?????????????????????????????????v????????±????????????????????????????????????????????°???????????????????????´??°
                d[e.t] = d[v] + e.c
                heappush(pq, (d[e.t], e.t)) #  python???heapq??????????°???????????????????pop?????????????????????????????§???-1??????????????????
    return d


def main(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break

        d = [[] for _ in range(n+1)]
        costs = [[float('inf')]*(n+1) for _ in range(n+1)]
        updated = False
        for _ in range(k):
            data = [int(x) for x in input().split()]
            if data[0] == 0:
                f, t = data[1], data[2]
                if updated:
                    costs[f] = dijkstra(f, d)
                if costs[f][t] == float('inf'):
                    print(-1)
                else:
                    print(costs[f][t])
            else:
                f, t, c = data[1], data[2], data[3]
                d[f].append(edge(t, c))
                d[t].append(edge(f, c))
                updated = True



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526
TLE
"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline


def dijkstra(s, G):
    pq = []
    d = [float('inf')] * len(G)
    d[s] = 0
    heappush(pq, (0, s))

    while pq:
        c, v = heappop(pq)
        if d[v] < c:
            continue
        for t, c in G[v].items():          #  ?????????v?????£??\??????????????±????????¨?????????????????°?????§?????????????????´??°
            if d[t] > d[v] + c: #  ???????????§??\??£?????????????????????????????????v????????±????????????????????????????????????????????°???????????????????????´??°
                d[t] = d[v] + c
                heappush(pq, (d[t], t)) #  python???heapq??????????°???????????????????pop?????????????????????????????§???-1??????????????????
    return d


def main(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break

        d = [{} for _ in range(n+1)]
        costs = [[float('inf')]*(n+1) for _ in range(n+1)]
        updated = False
        for _ in range(k):
            data = [int(x) for x in input().split()]
            if data[0] == 0:
                f, t = data[1], data[2]
                if updated:
                    costs[f] = dijkstra(f, d)
                if costs[f][t] == float('inf'):
                    print(-1)
                else:
                    print(costs[f][t])
            else:
                f, t, c = data[1], data[2], data[3]
                if t in d[f]:
                    d[f][t] = min(d[f][t], c)
                else:
                    d[f][t] = c
                if f in d[t]:
                    d[t][f] = min(d[t][f], c)
                else:
                    d[t][f] = c
                updated = True


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526

"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline


def dijkstra(s, G):
    pq = []
    d = [float('inf')] * len(G)
    d[s] = 0
    heappush(pq, (0, s))

    while pq:
        c, v = heappop(pq)
        if d[v] < c:
            continue
        for t, c in G[v].items():          #  ?????????v?????£??\??????????????±????????¨?????????????????°?????§?????????????????´??°
            if d[t] > d[v] + c: #  ???????????§??\??£?????????????????????????????????v????????±????????????????????????????????????????????°???????????????????????´??°
                d[t] = d[v] + c
                heappush(pq, (d[t], t)) #  python???heapq??????????°???????????????????pop?????????????????????????????§???-1??????????????????
    return d


def main(args):
    while True:
        n, k = map(int, input().split())
        if n == 0 and k == 0:
            break

        G = [{} for _ in range(n+1)]
        costs = [[float('inf')]*(n+1) for _ in range(n+1)]

        for _ in range(k):
            data = [int(x) for x in input().split()]
            if data[0] == 0:
                f, t = data[1], data[2]
                costs[f] = dijkstra(f, G)
                if costs[f][t] == float('inf'):
                    print(-1)
                else:
                    print(costs[f][t])
            else:
                f, t, c = data[1], data[2], data[3]
                if t in G[f]:
                    G[f][t] = min(G[f][t], c)
                else:
                    G[f][t] = c
                if f in G[t]:
                    G[t][f] = min(G[t][f], c)
                else:
                    G[t][f] = c


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Submission status: Accepted

Solution code:
def solve():
    max_fare = 99000001
    def dijkstra(start, goal):
        unvisited = [i for i in range(n)]
        fare = [max_fare] * n
        fare[start] = 0
        
        while True:
            min_fare = max_fare
            for i in unvisited:
                f = fare[i]
                if f < min_fare:
                    min_fare = f
                    u = i
                    
            if u == goal:
                return min_fare
            elif min_fare == max_fare:
                return -1
            
            unvisited.remove(u)
            
            for v, f in adj[u]:
                if v in unvisited:
                    fare[v] = min(min_fare + f, fare[v])
        
    import sys
    file_input = sys.stdin
    
    while True:
        n, k = map(int, file_input.readline().split())
        if n == 0 and k == 0:
            break
        
        adj = [[] for i in range(n)]
        
        for i in range(k):
            line = file_input.readline()
            if line[0] == '0':
                a, b = map(int, line[2:].split())
                print(dijkstra(a - 1, b - 1))
            else:
                c, d, e = map(int, line[2:].split())
                adj[c - 1].append((d - 1, e))
                adj[d - 1].append((c - 1, e))

solve()

Submission status: Accepted

Solution code:
def solve():
    from heapq import heappush, heappop
    def dijkstra(start, goal):
        fare = [99000001] * n
        fare[start] = 0
        pq = [(0, start)]
        
        while pq:
            u_fare, u = heappop(pq)
                    
            if u == goal:
                return u_fare
            
            for f, v in adj[u]:
                new_fare = u_fare + f
                if new_fare < fare[v]:
                    fare[v] = new_fare
                    heappush(pq, (new_fare, v))
        return -1
        
    import sys
    file_input = sys.stdin
    
    while True:
        n, k = map(int, file_input.readline().split())
        if n == 0 and k == 0:
            break
        
        adj = [[] for i in range(n)]
        
        for i in range(k):
            line = file_input.readline()
            if line[0] == '0':
                a, b = map(int, line[2:].split())
                print(dijkstra(a - 1, b - 1))
            else:
                c, d, e = map(int, line[2:].split())
                adj[c - 1].append((e, d - 1))
                adj[d - 1].append((e, c - 1))

solve()

Submission status: Accepted

Solution code:
from heapq import*
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,input().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)];E[d]+=[(e,c)]
  else:print(g(*f[1:]))

Submission status: Accepted

Solution code:
from heapq import*
def g(n,E,s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s():
 for e in iter(input,'0 0'):
  n,k=map(int,e.split())
  E=[[]for _ in[0]*-~n]
  for _ in[0]*k:
   f=[*map(int,input().split())]
   if f[0]:
    c,d,e=f[1:]
    E[c]+=[(e,d)];E[d]+=[(e,c)]
   else:print(g(n,E,*f[1:]))
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
import sys
from heapq import*
s=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,s().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)];E[d]+=[(e,c)]
  else:print(g(*f[1:]))

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(E,n,s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s():
 for e in iter(input,'0 0'):
  n,k=map(int,e.split())
  E=[[]for _ in[0]*-~n]
  for _ in[0]*k:
   f=[*map(int,r().split())]
   if f[0]:
    c,d,e=f[1:]
    E[c]+=[(e,d)];E[d]+=[(e,c)]
   else:print(g(E,n,*f[1:]))
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop
r=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,r().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)];E[d]+=[(e,c)]
  else:print(g(*f[1:]))

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,r().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)];E[d]+=[(e,c)]
  else:print(g(*f[1:]))

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,r().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)]
   E[d]+=[(e,c)]
  else:print(g(*f[1:]))

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=[*map(int,r().split())]
  if f[0]:
   c,d,e=f[1:]
   E[c]+=[(e,d)]
   E[d]+=[(e,c)]
  else:
   print(g(*f[1:]))

Submission status: Accepted

Solution code:
import sys
from heapq import*
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(input,'0 0'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=input()
  if'0'==f[0]:print(g(*map(int,f[2:].split())))
  else:
   c,d,e=map(int,f[2:].split())
   E[c]+=[(e,d)];E[d]+=[(e,c)]

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
for e in iter(r,'0 0\n'):
 n,k=map(int,e.split())
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(*map(int,f[2:].split())))
  else:
   c,d,e=map(int,f[2:].split())
   E[c]+=[(e,d)];E[d]+=[(e,c)]

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0
 H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
def s():
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  E=[[]for _ in[0]*-~n]
  for _ in[0]*k:
   f=r()
   if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
   else:
    c,d,e=map(int,f[2:].split())
    E[c]+=[(e,d)];E[d]+=[(e,c)]
s()

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0
 H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
def s():
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  E=[[]for _ in[0]*-~n]
  for _ in[0]*k:
   f=r()
   if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
   else:
    c,d,e=map(int,f[2:].split())
    E[c]+=[(e,d)];E[d]+=[(e,c)]
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
import sys
from heapq import*
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0
 H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:
   c,d,e=map(int,f[2:].split())
   E[c]+=[(e,d)];E[d]+=[(e,c)]
if'__main__'==__name__:
 for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0
 H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
if'__main__'==__name__:
 for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0
 H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:
    F[v]=t
    heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c=[*map(int,f[2:].split())];[E[c[i]].append([c[2],c[1-i]])for i in[0,1]]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[[e,d]];E[d]+=[[e,c]]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c].append([e,d]);E[d].append([e,c])
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   if c+f<F[v]:F[v]=c+f;heappush(H,(c+f,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   if c+f<F[v]:t=c+f;F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))

Submission status: Accepted

Solution code:
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
if'__main__'==__name__:
 for e in iter(r,'0 0\n'):s(*map(int,e.split()))