Problem:


問題 5:　タクシー (Taxis)

問題

IOI 国は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．IOI 国には K 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．車は道路を双方向に自由に移動できるが，道路以外を通ってある町から別の町に行くことはできない．

IOI 国の町 1 に住む JOI 君は，町 N に住む祖母の家までタクシーで行くことにした．IOI 国にはタクシー会社 1 からタクシー会社 N までの N 個のタクシー会社がある．IOI 国のタクシー会社には次のような少々特殊な規則がある．

タクシー会社 i のタクシーには，町 i でのみ乗車できる．

タクシー会社 i のタクシーの運賃は，利用した距離によらず Ci である．

タクシー会社 i のタクシーは，乗車してから連続して最大 Ri 本の道路しか通ることができない．

たとえば R1 = 2 の場合，町 1 からタクシー会社 1 のタクシーに乗車すると，最大 2 本の道路しか通ることができないため，道路を 3 本以上通るためには途中の町でタクシーを乗り換える必要がある．

JOI 君は町以外の地点でタクシーに乗ったりタクシーから降りたりすることはできない．また，タクシー以外の移動手段を用いることもできない．JOI 君が町 N に到達するために必要な運賃の合計の最小値を求めるプログラムを作成せよ．

入力

入力は 1 + N + K 行からなる．

1 行目には，2 つの整数 N, K (2 ≤ N ≤ 5000, N - 1 ≤ K ≤ 10000) が空白を区切りとして書かれている．これは，IOI 国が N 個の町からなることと，IOI 国の道路の本数が K 本であることを表す．

続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，2 つの整数 Ci, Ri (1 ≤ Ci ≤ 10000, 1 ≤ Ri ≤ N) が空白を区切りとして書かれている．これは，タクシー会社 i のタクシーの運賃が Ci で，乗車してから連続して最大 Ri 本の道路しか通ることができないことを表す．

続く K 行のうちの j 行目 (1 ≤ j ≤ K) には，異なる 2 つの整数 Aj, Bj (1 ≤ Aj ＜ Bj ≤ N) が空白を区切りとして書かれている．これは，町 Aj と町 Bj との間に道路が存在することを表す．同じ (Aj, Bj) の組が 2 回以上書かれていることはない．

与えられる入力データにおいては，どの町から別のどの町へもタクシーを乗り継いで行くことができることが保証されている．

出力

JOI 君が町 1 から町 N まで行くのに必要な運賃の合計の最小値を表す整数を 1 行で出力せよ．

入出力例

入力例
  

  

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

出力例

   

700

上の入出力例は，以下の図に対応している．円は町を，線は道路を表す．

この入出力例でJOI 君が最小の運賃で町 6 に到達するには，以下のようにする．

町 1 からタクシーに乗って町 5 に行く． (運賃 400)

町 5 からタクシーに乗って町 6 に行く． (運賃 300)

JOI 君がこのようなルートを通った場合の運賃の合計は 400 + 300 = 700 であるので，700 を出力する．

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



Sample input:
6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4


Sample output:
700

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def dijkstra(s,g,m):
    color=[0]*n
    dis=[float('inf')]*n
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v in g[u]:
            if color[v]!=2:
                if dis[u]+m[u][v]<dis[v]:
                    dis[v]=dis[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,k=map(int,raw_input().split())
cr=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[]*n for _ in xrange(n)]
for i in xrange(n):
    a,b=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

d=[[0]*n for _ in xrange(n)]
for i in xrange(n):
    q=deque([i])
    visited=[0]*n
    visited[i]=1
    while len(q)!=0:
        p=q.popleft()
        for j in g[p]:
            if visited[j]==0:
                visited[j]=1
                q.append(j)
                d[i][j]=d[i][p]+1

cost=[[float('inf')]*n for _ in xrange(n)]
newg=[[]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if d[i][j]<=cr[i][1]:
            cost[i][j]=cr[i][0]
            newg[i].append(j)

pq=[]
dis=dijkstra(0,newg,cost)
print(dis[n-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

def dijkstra(s,g,m):
    color=[0]*n
    dis=[float('inf')]*n
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v in g[u]:
            if color[v]!=2:
                if dis[u]+m[u][v]<dis[v]:
                    dis[v]=dis[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,k=map(int,raw_input().split())
cr=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[]*n for _ in xrange(n)]
for i in xrange(k):
    a,b=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
print g
d=[[0]*n for _ in xrange(n)]
for i in xrange(n):
    q=deque([i])
    visited=[0]*n
    visited[i]=1
    while len(q)!=0:
        p=q.popleft()
        for j in g[p]:
            if visited[j]==0:
                visited[j]=1
                q.append(j)
                d[i][j]=d[i][p]+1
                
cost=[[float('inf')]*n for _ in xrange(n)]
newg=[[]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if d[i][j]<=cr[i][1]:
            cost[i][j]=cr[i][0]
            newg[i].append(j)

pq=[]
dis=dijkstra(0,newg,cost)
print(dis[n-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[0] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a][b] = edges[b][a] = 1

costs = [INF for i in range(n)]
costs[0] = 0

def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in range(n) if edges[s_num][i]}
  ret = set()
  while loop - 1:
    new = set()
    for p in temp:
      pto = {i for i in range(n) if edges[p][i]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    loop -= 1
  return ret

costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  for num in to_lst:
    if costs[num] > next_cost:
      costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    push(que, (next_cost + clst[num], num))

print(costs[n - 1])

Submission status: Wrong Answer

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[0] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a][b] = edges[b][a] = 1

costs = [INF for i in range(n)]
costs[0] = 0

used = [False for i in range(n)]
def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in range(n) if edges[s_num][i]}
  ret = {i for i in temp}
  while loop:
    new = set()
    for p in temp:
      pto = {i for i in range(n) if edges[p][i]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    if not temp:
      break
    loop -= 1
  return ret

used[0] = True
costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  for num in to_lst:
    costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    if not used[num]:
      push(que, (costs[num] + clst[num], num))
      used[num] = True

print(costs[n - 1])
print(costs)

Submission status: Wrong Answer

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20

def main():
  n, k = map(int, input().split())
  
  clst = []
  rlst = []
  
  for i in range(n):
    c, r = map(int, input().split())
    clst.append(c)
    rlst.append(r)
  
  edges = [[] * n for i in range(n)]
  
  for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
  
  costs = [INF for i in range(n)]
  costs[0] = 0
  used = [False for i in range(n)]
  
  def make_to_lst(s_num):
    loop = rlst[s_num]
    temp = {i for i in edges[s_num]}
    ret = {i for i in temp}
    while loop:
      new = set()
      for p in temp:
        pto = {i for i in edges[p]}
        new = new | pto
      ret = ret | temp
      temp = new - ret
      if not temp:
        break
      loop -= 1
    return ret
  
  used[0] = True
  costs[0] = 0
  break_flag = 0
  que = [(clst[0], 0)]
  
  while que and not break_flag:
    next_cost, s_num = pop(que)
    to_lst = make_to_lst(s_num)

    for num in to_lst:
      costs[num] = next_cost
      if num == n - 1:
        break_flag = 1
        break
      if not used[num]:
        push(que, (costs[num] + clst[num], num))
        used[num] = True
  
  print(costs[num - 1])

main()

Submission status: Accepted

Solution code:
from collections import deque
import heapq

def dijkstra(s,g,m):
    color=[0]*n
    dis=[float('inf')]*n
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v in g[u]:
            if color[v]!=2:
                if dis[u]+m[u][v]<dis[v]:
                    dis[v]=dis[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,k=map(int,raw_input().split())
cr=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[]*n for _ in xrange(n)]
for i in xrange(k):
    a,b=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    
d=[[0]*n for _ in xrange(n)]
for i in xrange(n):
    q=deque([i])
    visited=[0]*n
    visited[i]=1
    while len(q)!=0:
        p=q.popleft()
        for j in g[p]:
            if visited[j]==0:
                visited[j]=1
                q.append(j)
                d[i][j]=d[i][p]+1

cost=[[float('inf')]*n for _ in xrange(n)]
newg=[[]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if d[i][j]<=cr[i][1]:
            cost[i][j]=cr[i][0]
            newg[i].append(j)

pq=[]
dis=dijkstra(0,newg,cost)
print(dis[n-1])

Submission status: Accepted

Solution code:
from collections import deque
import heapq

def dijkstra(s,g,m):
    color=[0]*n
    dis=[float('inf')]*n
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v in g[u]:
            if color[v]!=2:
                if dis[u]+m[u][v]<dis[v]:
                    dis[v]=dis[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,k=map(int,raw_input().split())
cr=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[]*n for _ in xrange(n)]
for i in xrange(k):
    a,b=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

d=[[0]*n for _ in xrange(n)]
cost=[[float('inf')]*n for _ in xrange(n)]
newg=[[]*n for _ in xrange(n)]
for i in xrange(n):
    q=deque([i])
    visited=[0]*n
    visited[i]=1
    while len(q)!=0:
        p=q.popleft()
        for j in g[p]:
            if visited[j]==0:
                visited[j]=1
                d[i][j]=d[i][p]+1
                if d[i][j]<=cr[i][1]:
                    cost[i][j]=cr[i][0]
                    newg[i].append(j)
                    q.append(j)

pq=[]
dis=dijkstra(0,newg,cost)
print(dis[n-1])

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[0] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a][b] = edges[b][a] = 1

costs = [INF for i in range(n)]
costs[0] = 0

used = [False for i in range(n)]
def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in range(n) if edges[s_num][i]}
  ret = {i for i in temp}
  while loop:
    new = set()
    for p in temp:
      pto = {i for i in range(n) if edges[p][i]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    if not temp:
      break
    loop -= 1
  return ret

used[0] = True
costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  for num in to_lst:
    costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    if not used[num]:
      push(que, (costs[num] + clst[num], num))
      used[num] = True

print(costs[n - 1])

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a].append(b)
  edges[b].append(a)

costs = [INF for i in range(n)]
costs[0] = 0
used = [False for i in range(n)]

def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in edges[s_num]}
  ret = {i for i in temp}
  while loop:
    new = set()
    for p in temp:
      pto = {i for i in edges[p]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    if not temp:
      break
    loop -= 1
  return ret

used[0] = True
costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  for num in to_lst:
    costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    if not used[num]:
      push(que, (costs[num] + clst[num], num))
      used[num] = True

print(costs[n - 1])

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20

def main():
  n, k = map(int, input().split())
  
  clst = []
  rlst = []
  
  for i in range(n):
    c, r = map(int, input().split())
    clst.append(c)
    rlst.append(r)
  
  edges = [[] * n for i in range(n)]
  
  for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
  
  costs = [INF for i in range(n)]
  costs[0] = 0
  used = [False for i in range(n)]
  
  def make_to_lst(s_num):
    loop = rlst[s_num]
    temp = {i for i in edges[s_num]}
    ret = {i for i in temp}
    while loop:
      new = set()
      for p in temp:
        pto = {i for i in edges[p]}
        new = new | pto
      ret = ret | temp
      temp = new - ret
      if not temp:
        break
      loop -= 1
    return ret
  
  used[0] = True
  costs[0] = 0
  break_flag = 0
  que = [(clst[0], 0)]
  
  while que and not break_flag:
    next_cost, s_num = pop(que)
    to_lst = make_to_lst(s_num)

    for num in to_lst:
      costs[num] = next_cost
      if num == n - 1:
        break_flag = 1
        break
      if not used[num]:
        push(que, (costs[num] + clst[num], num))
        used[num] = True
  
  print(costs[n - 1])

main()

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20

def main():
  n, k = map(int, input().split())
  
  clst = []
  rlst = []
  
  for i in range(n):
    c, r = map(int, input().split())
    clst.append(c)
    rlst.append(r)
  
  edges = [[] * n for i in range(n)]
  
  for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
  
  costs = [INF for i in range(n)]
  costs[0] = 0
  used = [False for i in range(n)]
  
  def make_to_lst(s_num):
    loop = rlst[s_num]
    temp = set(edges[s_num])
    ret = set()
    while loop:
      new = set()
      for p in temp:
        pto = set(edges[p])
        new = new | pto
      ret = ret | temp
      temp = new - ret
      if not temp:
        break
      loop -= 1
    return ret
  
  used[0] = True
  costs[0] = 0
  break_flag = 0
  que = [(clst[0], 0)]
  
  while que and not break_flag:
    next_cost, s_num = pop(que)
    to_lst = make_to_lst(s_num)

    for num in to_lst:
      costs[num] = next_cost
      if num == n - 1:
        break_flag = 1
        break
      if not used[num]:
        push(que, (costs[num] + clst[num], num))
        used[num] = True
  
  print(costs[n - 1])

main()

Submission status: Accepted

Solution code:
from heapq import heappop as pop
from heapq import heappush as push

def main():
  n, k = map(int, input().split())
  
  clst = []
  rlst = []
  
  for i in range(n):
    c, r = map(int, input().split())
    clst.append(c)
    rlst.append(r)
  
  edges = [[] * n for i in range(n)]
  
  for i in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
  
  costs = [None] * n
  used = [False] * n
  
  def make_to_lst(s_num):
    loop = rlst[s_num]
    temp = set(edges[s_num])
    ret = set()
    while loop and temp:
      new = set()
      for p in temp:
        pto = set(edges[p])
        new = new | pto
      ret = ret | temp
      temp = new - ret
      loop -= 1
    return ret
  
  used[0] = True
  costs[0] = 0
  que = [(clst[0], 0)]
  
  while que:
    next_cost, s_num = pop(que)
    to_lst = make_to_lst(s_num)

    for num in to_lst:
      if num == n - 1:
        print(next_cost)
        return

      costs[num] = next_cost

      if not used[num]:
        push(que, (next_cost + clst[num], num))
        used[num] = True
  

main()

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq

def dijkstra(s,g,m):
    color=[0]*n
    dis=[float('inf')]*n
    dis[s]=0
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        color[u]=2
        if dis[u]<t:
            continue
        for v in g[u]:
            if color[v]!=2:
                if dis[u]+m[u][v]<dis[v]:
                    dis[v]=dis[u]+m[u][v]
                    color[v]=1
                    heapq.heappush(pq,[dis[v],v])
    return dis

n,k=map(int,raw_input().split())
cr=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[]*n for _ in xrange(n)]
m=[[0]*n for _ in xrange(n)]
for i in xrange(k):
    a,b=map(int,raw_input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    m[a-1][b-1]=1
    m[b-1][a-1]=1

pq=[]
d=[[]*n for _ in xrange(n)]
for i in xrange(n):
    d[i]=dijkstra(i,g,m)

cost=[[float('inf')]*n for _ in xrange(n)]
newg=[[]*n for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(n):
        if d[i][j]<=cr[i][1]:
            cost[i][j]=cr[i][0]
            newg[i].append(j)

pq=[]
dis=dijkstra(0,newg,cost)
print(dis[n-1])

Submission status: Runtime Error

Solution code:
def calcm(x):
    gone = [set([x])]
    for _ in range(a[x][1]):
        gone.append(set())
        for i in gone[-2]:
            for j in link[i]:
                for k in gone:
                    if j in k:
                        break
                else:
                    gone[-1].add(j)
    minq = []
    for i in gone[1:]:
        for j in i:
            if cost[x] + a[x][0] < cost[j]:
                cost[j] = cost[x] + a[x][0]
                minq.append(j)
    for i in minq:
        calcm(i)
    
    

n, m = map(int, input().split())
a = [0] + [list(map(int, input().split())) for _ in range(n)]
link = [[] for _ in range(n + 1)]
cost = [1e10 for _ in range(n + 1)]
cost[1] = 0
for _ in range(m):
    v1, v2 = map(int, input().split())
    link[v1].append(v2)
    link[v2].append(v1)
calcm(1)
print(cost[n])

Submission status: Runtime Error

Solution code:
from heapq import heappop as pop
from heapq import heappush as push
INF = 10 ** 20
n, k = map(int, input().split())

clst = []
rlst = []

for i in range(n):
  c, r = map(int, input().split())
  clst.append(c)
  rlst.append(r)

edges = [[0] * n for i in range(n)]

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a][b] = edges[b][a] = 1

costs = [INF for i in range(n)]
costs[0] = 0

def make_to_lst(s_num):
  loop = rlst[s_num]
  temp = {i for i in range(n) if edges[s_num][i]}
  ret = {i for i in temp}
  while loop - 1:
    new = set()
    for p in temp:
      pto = {i for i in range(n) if edges[p][i]}
      new = new | pto
    ret = ret | temp
    temp = new - ret
    loop -= 1
  return ret

costs[0] = 0
break_flag = 0
que = [(clst[0], 0)]

while que and not break_flag:
  next_cost, s_num = pop(que)
  to_lst = make_to_lst(s_num)
  
  for num in to_lst:
    if costs[num] > next_cost:
      costs[num] = next_cost
    if num == n - 1:
      break_flag = 1
      break
    push(que, (next_cost + clst[num], num))

print(costs[n - 1])