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: Wrong Answer

Solution code:
inf = 2**31

def dijkstra(s):
    d = [inf]*n
    used = [False]*n
    d[s] = 0
    while 1:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]): v = u
        
        if v == -1: break
        used[v] = True
        for u in range(n):
            d[u] = min(d[u],d[v]+G[v][u])
    return d

n,k = map(int,raw_input().split())
G = [[inf]*n for _ in range(n)]
for roop in range(k):
    inp = map(int,raw_input().split())
    if len(inp) == 3:
        a,b = inp[1:]
        ans = dijkstra(a-1)[b-1]
        print ans if ans < inf else -1
    else:
        c,d,e = inp[1:]
        G[c-1][d-1] = G[d-1][c-1] = e

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

# 0526 Boat Travel

import sys

# 再帰の最大回数を設定
LIMIT = 100000
sys.setrecursionlimit(LIMIT)

INF = 1e9

def main():
    # 入力
    (n, k) = map(int, raw_input().split())
    data = [map(int, raw_input().split()) for x in xrange(k)]

    for x in solve(data, n):
        print(x)

def solve(data, n):
    # 船舶の運賃
    boat = {}
    used = {}
    cost = {x+1:INF for x in xrange(n)}

    def makeBoat(island1, island2, value):
        if (island1, island2) in boat:
            if boat[(island1, island2)] > value:
                boat[(island1, island2)] = value
                boat[(island2, island1)] = value
        else:
            boat[(island1, island2)] = value
            boat[(island2, island1)] = value

    def decisionValue(island1, island2):
        used[island1] = True

        # 隣接ノードを探索
        adj_island = filter(lambda x:(island1, x) in boat, cost)

        # 既訪ノードを削除
        adj_island = filter(lambda x:x not in used, adj_island)

        # コストを更新
        for x in adj_island:
            if cost[x] > cost[island1] + boat[(island1, x)]:
                cost[x] = cost[island1] + boat[(island1, x)]
            else:
                pass

        # 未訪ノードから最小点について再帰
        yet_node = filter(lambda x:x not in used, cost)
        if len(yet_node) == 0:
            if cost[island2] == INF:
                return -1
            else:
                return cost[island2]
        else:
            min_node = min(yet_node, key=lambda x:cost[x])
            return decisionValue(min_node, island2)

    for x in data:
        if x[0] == 1:
            makeBoat(*x[1:])
        else:
            cost[x[1]] = 0
            yield decisionValue(*x[1:])
            used = {}
            cost = {x+1:INF for x in xrange(n)}

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF = 1<<29
n, k = map(int, raw_input().split())
dist = [[INF]*n for i in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(k):
    q = map(int, raw_input().split())
    a = q[1] - 1; b = q[2] - 1;
    if q[0] == 0:
        print -1 if dist[a][b] == INF else dist[a][b]
    else:
        dist[a][b] = dist[b][a] = min(dist[a][b], q[3])
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][a] + dist[a][b] + dist[b][j])
                dist[i][j] = min(dist[i][j], dist[i][b] + dist[b][a] + dist[a][j])

Submission status: Wrong Answer

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)]
    connected = [{i} for i 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))
            connected[c].update(connected[d])
            connected[d] = connected[c]
        else:
            a, b = o
            a, b = a - 1, b - 1
            print(dijkstra(a, b, links) if b in connected[a] else -1)

Submission status: Wrong Answer

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)
                    costs[t] = dijkstra(t, d)
                    updated = False
                cost = min(costs[f][t], costs[t][f])
                if cost == 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: Wrong Answer

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)
                    updated = False
                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


def dijkstra2(d, s, G):
    pq = []
    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??????????????????


def main2(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)]
        need_update = False

        for _ in range(k):
            data = [int(x) for x in input().split()]
            if data[0] == 0:
                f, t = data[1], data[2]
                if need_update:
                    dijkstra2(costs[f], 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
                need_update = True


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

Submission status: Wrong Answer

Solution code:
def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
s()

Submission status: Time Limit Exceeded

Solution code:
inf = 2**31

def dijkstra(s):
    d = [inf]*n
    used = [False]*n
    d[s] = 0
    while 1:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]): v = u
        
        if v == -1: break
        used[v] = True
        for u in range(n):
            d[u] = min(d[u],d[v]+G[v][u])
    return d

while 1:
    n,k = map(int,raw_input().split())
    if n == k == 0: break
    G = [[inf]*n for _ in range(n)]
    for roop in range(k):
        inp = map(int,raw_input().split())
        if len(inp) == 3:
            a,b = inp[1:]
            ans = dijkstra(a-1)[b-1]
            print ans if ans < inf else -1
        else:
            c,d,e = inp[1:]
            G[c-1][d-1] = G[d-1][c-1] = e

Submission status: Time Limit Exceeded

Solution code:
INF = 1<<29
while 1:
    n, k = map(int, raw_input().split())
    if n == 0 : break
    dist = [[INF]*n for i in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i in range(k):
        q = map(int, raw_input().split())
        a = q[1] - 1; b = q[2] - 1;
        if q[0] == 0:
            print -1 if dist[a][b] == INF else dist[a][b]
        else:
            dist[a][b] = dist[b][a] = min(dist[a][b], q[3])
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][a] + dist[a][b] + dist[b][j])
                    dist[i][j] = min(dist[i][j], dist[i][b] + dist[b][a] + dist[a][j])

Submission status: Time Limit Exceeded

Solution code:
INF = 1<<29
while 1:
    n, k = map(int, raw_input().split())
    if n == 0 : break
    dist = [[INF]*n for i in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i in range(k):
        q = map(int, raw_input().split())
        a = q[1] - 1; b = q[2] - 1;
        if q[0] == 0:
            print -1 if dist[a][b] == INF else dist[a][b]
        else:
            dist[a][b] = dist[b][a] = min(dist[a][b], q[3])
            for i in range(n):
                for j in range(i,n):
                    dist[i][j] = min(dist[i][j], dist[i][a] + dist[a][b] + dist[b][j], dist[i][b] + dist[b][a] + dist[a][j])
                for j in range(i,n):
                    dist[j][i] = dist[i][j]

Submission status: Time Limit Exceeded

Solution code:
import sys

def dijkstra(nodes, start, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  counter = 0
  while True:
    counter += 1
    if counter == nodes or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    node = minnode

while True:
  n,k = map(int, raw_input().split())
  if n==k==0:
    break
  matrix = [[sys.maxint] * n for i in xrange(n)]
  for i in xrange(k):
    ri = raw_input().split()
    if ri[0] == "0":
      # check price
      a = int(ri[1])
      b = int(ri[2])
      price = dijkstra(n, a-1, matrix)[b-1]
      if price == sys.maxint:
        print "-1"
      else:
        print price
    else:
      # add path
      c = int(ri[1])
      d = int(ri[2])
      e = int(ri[3])
      matrix[c-1][d-1] = min(matrix[c-1][d-1], e)
      matrix[d-1][c-1] = min(matrix[d-1][c-1], e)

Submission status: Time Limit Exceeded

Solution code:
import sys

def dijkstra(nodes, start, matrix):
  defnode = [False] * (nodes)
  cost = [sys.maxint] * (nodes)
  cost[start] = 0
  node = start
  counter = 0
  while True:
    counter += 1
    if counter == nodes or node == sys.maxint:
      return cost
    defnode[node] = True
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if matrix[node][i] == sys.maxint:
        continue
      cost[i] = min(cost[i], cost[node]+matrix[node][i])
    minnode = sys.maxint
    mincost = sys.maxint
    for i in xrange(nodes):
      if defnode[i]:
        continue
      if cost[i] < mincost:
        minnode = i
        mincost = cost[i]
    node = minnode

inlines = sys.stdin.readlines()
it = 0
while True:
  st = inlines[it]
  n,k = map(int, st.split())
  if n==k==0:
    break
  it += 1
  matrix = [[sys.maxint] * n for i in xrange(n)]
  for i in xrange(k):
    st = inlines[it]
    ri = st.split()
    if ri[0] == "0":
      # check price
      a = int(ri[1])
      b = int(ri[2])
      price = dijkstra(n, a-1, matrix)[b-1]
      if price == sys.maxint:
        print "-1"
      else:
        print price
    else:
      # add path
      c = int(ri[1])
      d = int(ri[2])
      e = int(ri[3])
      matrix[c-1][d-1] = min(matrix[c-1][d-1], e)
      matrix[d-1][c-1] = min(matrix[d-1][c-1], e)
    it += 1

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(n, ds):
    for k in range(n):
        ds_k = ds[k]
        for i in range(n):
            ds_i = ds[i]
            ds_i_k = ds_i[k]
            for j in range(n):
                ds_i[j] = min(ds_i[j], ds_i_k + ds_k[j])
    return ds


while True:
    n, k = map(int, input().split())
    if not n:
        break
    ds = [[0 if i == j else float('inf') for j in range(n)] for i in range(n)]
    pre_op = 0
    for _ in range(k):
        o = map(int, input().split())
        op = next(o)
        if op:
            c, d, e = o
            c, d = c - 1, d - 1
            ds[c][d] = ds[d][c] = min(e, ds[c][d])
        else:
            a, b = o
            if pre_op:
                ds = warshall_floyd(n, ds)
            ans = ds[a - 1][b - 1]
            print(-1 if ans == float('inf') else ans)
        pre_op = op

Submission status: Time Limit Exceeded

Solution code:
while(1):
    [n,m]=map(int,raw_input().split())
    if n==0: break
    largenum=100000*10000
    A=[[largenum for i in range(n)] for j in range(n)]
    for i in range(n):
        A[i][i]=0
        
    for i in range(m):
        q=map(int,raw_input().split())
        if q[0]==0:
            p=A[q[1]-1][q[2]-1]
            if p>=largenum:    print -1
            else:    print p
        else:
            for i in range(n):
                for j in range(n):
                    a,b,c=q[1:]
                    a-=1
                    b-=1
                    np=min(A[i][j],A[i][a]+c+A[b][j],A[i][b]+c+A[a][j])
                    A[i][j]=np
                    A[j][i]=np

Submission status: Time Limit Exceeded

Solution code:
while(1):
    [n,m]=map(int,raw_input().split())
    if n==0: break
    largenum=100000*10000
    A=[[largenum for i in range(n)] for j in range(n)]
    for i in range(n):
        A[i][i]=0
        
    for i in range(m):
        q=map(int,raw_input().split())
        if q[0]==0:
            p=A[q[1]-1][q[2]-1]
            if p>=largenum:    print -1
            else:    print p
        else:
            for i in range(n):
                for j in range(i):
                    a,b,c=q[1:]
                    a-=1
                    b-=1
                    np=min(A[i][j],A[i][a]+c+A[b][j],A[i][b]+c+A[a][j])
                    A[i][j]=np
                    A[j][i]=np

Submission status: Time Limit Exceeded

Solution code:
inf = 10**6+1

def warshall_floyd():
    global n
    global cost
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if cost[i][j] > cost[j][k]+cost[k][i]:
                    cost[i][j] = cost[j][k]+cost[k][i]



while True:
    n,k = map(int, input().split())
    if (n|k)==0: break
    flag = True

    cost = [[inf]*n for i in range (n)]
    for inline in range(k):
        query = list(map(int, input().split()))
        if query[0]:
            cost[query[1]-1][query[2]-1] = min(cost[query[1]-1][query[2]-1], query[3])
            cost[query[2]-1][query[1]-1] = cost[query[1]-1][query[2]-1]
            flag = True
        else:
            if flag: warshall_floyd()
            mon = cost[query[1]-1][query[2]-1]
            print(mon if mon != inf else -1)
            flag = False

Submission status: Time Limit Exceeded

Solution code:

inf = 10**6+1

def dijkstra(a,b):
    global inf
    global n
    global cost

    d = [inf]*n
    d[a] = 0
    prev= [-1]*n
    q = [1]*n

    for _ in range(n):
        pmin = inf
        u = inf
        for ki in range(n):
            if pmin>=d[ki] and q[ki]:
                pmin = d[ki]
                u = ki

        q[u] = 0
        for v in range(n):
            if cost[u][v] != inf:
                if d[v] > d[u] + cost[u][v]:
                    d[v] = d[u] + cost[u][v]
                    prev[v] = u

    return d[b]


while True:
    n,k = map(int, input().split())
    if (n|k)==0: break

    cost = [[inf]*n for i in range (n)]
    for inline in range(k):
        query = list(map(int, input().split()))
        if query[0]:
            cost[query[1]-1][query[2]-1] = min(cost[query[1]-1][query[2]-1], query[3])
            cost[query[2]-1][query[1]-1] = cost[query[1]-1][query[2]-1]
        else:
            mon = dijkstra(query[1]-1,query[2]-1)
            print(mon if mon != inf else -1)

Submission status: Time Limit Exceeded

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 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 main(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


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

Submission status: Time Limit Exceeded

Solution code:
#elst...i->j = elst[i]j[]
#vlst...[mincost, ...]
INF = 1000000000

def dyc(n,elst,start,goal):
  vlst = [INF for i in range(n)]
  ulst = [0 for i in range(n)]
  vlst[start] = 0
  while True:
    v = -1
    for i in range(n):
      if(ulst[i] == 0 and (v == -1 or vlst[i] < vlst[v])):
        v = i
    if v == -1:
      break
    ulst[v] = 1
    for i in range(n):
      vlst[i] = min(vlst[i], vlst[v] + elst[v][i])
  if vlst[goal] >= INF:
    print(-1)
  else:
    print(vlst[goal])
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    elst = [[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:
        dyc(n, elst, lst[1] - 1, lst[2] - 1)
      elif lst[0] == 1:
        elst[lst[1] - 1][lst[2] - 1] = min(lst[3],elst[lst[1] - 1][lst[2] - 1])
        elst[lst[2] - 1][lst[1] - 1] = min(lst[3],elst[lst[2] - 1][lst[1] - 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
    vlst = [[INF if i != j else 0 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:
        if vlst[lst[1] - 1][lst[2] - 1] >= INF:
          print(-1)
        else:
          print(vlst[lst[1] - 1][lst[2] - 1])
      elif lst[0] == 1:
        for i in range(n):
          for j in range(n):
            vlst[i][j] = min(vlst[i][j],vlst[i][lst[1] - 1] + lst[3] + vlst[lst[2] - 1][j])
            vlst[j][i] = vlst[i][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 = [[INF if i != j else 0 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:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        if D[a - 1][b - 1] >= INF:
          print(-1)
        else:
          print(D[lst[1] - 1][lst[2] - 1])
      elif lst[0] == 1:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        for i in range(n):
          for j in range(i,n):
            D[i][j] = min(D[i][j],D[i][a - 1] + lst[3] + D[b - 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 = [[INF if i != j else 0 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])
        if D[b - 1][a - 1] >= INF:
          print(-1)
        else:
          print(D[b - 1][a - 1])
      elif lst[0] == 1:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        D[b-1][a-1] = min(D[b-1][a-1],lst[3])
        for i in range(n):
          for j in range(0,i + 1):
            D[i][j] = min(D[i][j],D[max(i,a-1)][min(i,a-1)] + lst[3] + D[max(j,b-1)][min(j,b-1)],D[max(i,b-1)][min(i,b-1)] + lst[3] + D[max(j,a-1)][min(j,a-1)])
  except EOFError:
    break

Submission status: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(s,0)]
  U = [0 for i in range(n)]
  while V:
    v = V.pop(0)
    U[v[0]] = 1
    for e in E[v[0]]:
      if U[e[0]] == 0 and D[v[0]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[0]] + e[1]
        V.append((e[0],D[e[0]]))
        V = sorted(V,key=lambda x:x[1])
  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()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        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: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  U = [0 for i in range(n)]
  while V:
    v = V.pop(0)
    U[v[1]] = 1
    for e in E[v[1]]:
      if U[e[0]] == 0 and D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  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()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        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: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  while V:
    v = V.pop(0)
    for e in E[v[1]]:
      if D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  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()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        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: Time Limit Exceeded

Solution code:
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [s]
  while V:
    v = V.pop(0)
    for e in E[v]:
      if D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
  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 = [INF for i in range(n)]
  D[s] = 0
  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 U[e[0]] == 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