Problem:


鉄道路線

ある国の鉄道網に、自動改札を導入することになりました。導入にあたって難しい問題の一つは、与えられた切符で、指定された駅の間を移動できるかどうかを判定することです。それぞれの切符には乗車駅と降車駅が記載されています。この切符でできるのは、「乗車駅で乗って、降車駅で降りる」ことだけではなく、途中乗車や途中下車も許されています。

この鉄道網にはS 個の駅があり、そのうちR 組の駅は隣り合っていて、他の駅を経由せずに双方向に鉄道で移動することができます。隣り合った駅を結ぶ線路はひとつしかありません。隣り合った駅の間の距離は、この線路に沿って測った距離です。ある駅からある駅までの経路は鉄道網の形状によっては複数通り考えられますが、そのうち最も距離が短くなるような経路を最短経路と呼ぶことにします。そのような経路が複数ある場合、どちらも最短経路として認められます。

乗車駅 a、降車駅 b の切符で駅 c から駅 d まで移動できるのは、以下の条件をすべて満たす経路 p が存在するときです。

 経路 p は、駅 a から駅 b への最短経路である。

 経路 p は、駅 a から出発し、駅 c、駅 d の順に経由し、駅 b で終わる経路である。また、駅 c から駅 d の区間はこの2 駅の最短経路になっている。

路線図と切符の情報が与えられます。次に、始点と終点の組がいくつか与えられるので、その切符で始点から終点へ移動できるかどうかを判定するプログラムを作成してください。

入力

入力は１つのデータセットからなる。入力データは以下の形式で与えられる。

S R
u1 v1 w1
u2 v2 w2
:
uR vR wR
a b Q
c1 d1
:
cQ dQ

各行で与えられる数値は１つの空白で区切られている。

１行目は２つの整数からなる。S (2 ≤ S ≤ 100000) は鉄道路線図に現れる駅の数、R (1 ≤ R ≤ 200000) は隣り合った駅の組の数である。続く R 行に、隣り合った駅の間を直接つなぐ線路の情報が与えられる。ui と vi (1 ≤ ui, vi ≤ S) は i 番目の線路の両端の駅の番号を示す。wi (1 ≤ wi ≤ 1000) はこれらの駅の間の距離を表す整数である。ただし、各駅には 1 から S までの番号が重複なく割り振られており、ui &ne; vi とする。

続く１行は３つの整数からなる。最初の２つの整数は切符の区間を表し、a は乗車駅、b は降車駅 (1 ≤ a, b ≤ S) である。３つ目の整数 Q (1 ≤ Q ≤ 40000) は質問の数を示す。続く Q 行に質問が与えられる。 ci とdi (1 ≤ ci, di ≤ S)は i 番目の質問の乗車駅と降車駅を示す。ただし、a &ne; b、ci &ne; di とする。

出力

質問ごとに、与えられた切符で移動できるなら Yes を、できないなら No を１行に出力する。

入力例

6 7
1 2 3
1 4 1
2 3 5
4 3 1
3 6 2
4 5 2
5 6 1
1 6 6
1 6
4 3
4 6
5 6
2 6
2 5

出力例

Yes
Yes
Yes
Yes
No
No



Sample input:
6 7
1 2 3
1 4 1
2 3 5
4 3 1
3 6 2
4 5 2
5 6 1
1 6 6
1 6
4 3
4 6
5 6
2 6
2 5


Sample output:
Yes
Yes
Yes
Yes
No
No

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

def main():
  INF = 10 ** 20
  s, r = map(int, input().split())
  
  edges = [[] for _ in range(s)]
  for _ in range(r):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, w))
    edges[v].append((u, w))
  
  a, b, q = map(int, input().split())
  a -= 1
  b -= 1
  costs = [(INF, [])] * s
  costs[a] = (0, [[a]])
  que = []
  heappush(que, a)
  while que:
    node = heappop(que)
    total, paths = costs[node]
    for to, weight in edges[node]:
      to_total, to_paths = costs[to]
      if to_total > total + weight:
        costs[to] = (total + weight, [lst + [to] for lst in paths])
        heappush(que, to)
      elif to_total == total + weight:
        costs[to] = (to_total, to_paths + [lst + [to] for lst in paths])
  
  
  _, atob = costs[b]
  from_to = [set() for _ in range(s)]
  for path in atob:
    for i, p in enumerate(path):
      from_to[p] = from_to[p] | set(path[i + 1:])
  
  for _ in range(q):
    start, goal = map(int, input().split())
    start -= 1
    goal -= 1
    if goal in from_to[start]:
      print("Yes")
    else:
      print("No")

main()

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappush, heappop

def main():
  INF = 10 ** 20
  s, r = map(int, input().split())
  
  edges = [[] for _ in range(s)]
  for _ in range(r):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, w))
    edges[v].append((u, w))
  
  a, b, q = map(int, input().split())
  a -= 1
  b -= 1
  costs = [(INF, [])] * s
  costs[a] = (0, [[a]])
  que = []
  heappush(que, (0, a))
  while que:
    dist, node = heappop(que)
    total, paths = costs[node]
    for to, weight in edges[node]:
      to_total, to_paths = costs[to]
      if to_total > total + weight:
        costs[to] = (total + weight, [lst + [to] for lst in paths])
        heappush(que, (total + weight, to))
      elif to_total == total + weight:
        costs[to] = (to_total, to_paths + [lst + [to] for lst in paths])
  
  
  _, atob = costs[b]
  from_to = [set() for _ in range(s)]
  for path in atob:
    for i, p in enumerate(path):
      from_to[p] = from_to[p] | set(path[i + 1:])
  
  for _ in range(q):
    start, goal = map(int, input().split())
    start -= 1
    goal -= 1
    if goal in from_to[start]:
      print("Yes")
    else:
      print("No")

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

s, r = map(int, input().split())
edges = [[] for _ in range(s)]
for _ in range(r):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, w))
    edges[v].append((u, w))

a, b, q = map(int, input().split())
a -= 1
b -= 1


def dijkstra(start):
    INF = 10 ** 20
    dist = [INF] * s
    dist[start] = 0
    parents = [[] for _ in range(s)]
    que = []
    heappush(que, (0, start))
    while que:
        score, node = heappop(que)
        for to, w in edges[node]:
            if dist[to] > score + w:
                dist[to] = score + w
                parents[to] = {node}
                heappush(que, (score + w, to))
            elif dist[to] == score + w:
                parents[to].add(node)
    return dist, parents


def on_shortest_path(c, d, mem):
    if c == d:return True
    if d in mem:return False
    mem.add(d)
    if dist_from_a[c] >= dist_from_a[d]:return False
    for parent in parents[d]:
        if on_shortest_path(c, parent, mem):return True
    return False


dist_from_a, parents = dijkstra(a)
dist_from_b, _ = dijkstra(b)
shortest = dist_from_a[b]
for _ in range(q):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if dist_from_a[c] + dist_from_b[c] == shortest and \
       dist_from_a[d] + dist_from_b[d] == shortest and \
       on_shortest_path(c, d, set()):
        print("Yes")
    else:
        print("No")