Problem:


Score : 700 points

Problem Statement

We have a graph with N vertices and M edges, and there are two people on the graph: Takahashi and Aoki.

The i-th edge connects Vertex U_i and Vertex V_i.
The time it takes to traverse this edge is D_i minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).

Takahashi departs Vertex S and Aoki departs Vertex T at the same time. Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo 10^9 + 7.

Constraints

1 \leq N \leq 100 000

1 \leq M \leq 200 000

1 \leq S, T \leq N

S \neq T

1 \leq U_i, V_i \leq N (1 \leq i \leq M)

1 \leq D_i \leq 10^9 (1 \leq i \leq M)

If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).

U_i \neq V_i (1 \leq i \leq M)

D_i are integers.

The given graph is connected.

Input

Input is given from Standard Input in the following format:

N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

Output

Print the answer.

Sample Input 1

4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1

Sample Output 1

2

There are two ways to choose shortest paths that satisfies the condition:

Takahashi chooses the path 1 \rightarrow 2 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 4 \rightarrow 1.

Takahashi chooses the path 1 \rightarrow 4 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 2 \rightarrow 1.

Sample Input 2

3 3
1 3
1 2 1
2 3 1
3 1 2

Sample Output 2

2

Sample Input 3

3 3
1 3
1 2 1
2 3 1
3 1 2

Sample Output 3

2

Sample Input 4

8 13
4 2
7 3 9
6 2 3
1 6 4
7 6 9
3 8 9
1 2 2
2 8 12
8 6 9
2 5 5
4 2 18
5 3 7
5 1 515371567
4 8 6

Sample Output 4

6



Sample input:
4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    s, t = map(lambda x: int(x)-1, input().split())
    uvd = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append((b-1, c)) for a, b, c in uvd]
    [g[b-1].append((a-1, c)) for a, b, c in uvd]

    import heapq
    inf = 10**16
    mod = 10**9+7

    dist_s = [inf]*n
    dp_s = ([0]*n)+[1]
    h = [(0, s, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_s[i] == inf:
            dist_s[i] = d
            dp_s[i] = dp_s[a]
            for j, k in g[i]:
                if dist_s[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_s[i] == d:
            dp_s[i] = (dp_s[i]+dp_s[a]) % mod

    dist_t = [inf]*n
    dp_t = ([0]*n)+[1]
    h = [(0, t, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_t[i] == inf:
            dist_t[i] = d
            dp_t[i] = dp_t[a]
            for j, k in g[i]:
                if dist_t[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_t[i] == d:
            dp_t[i] = (dp_t[i]+dp_t[a]) % mod

    ans = dp_s[t]**2 % mod
    short = dist_s[t]

    point = []
    path = []

    for i in range(n):
        d = dist_s[i]*2
        if d == short and dist_t[i]*2 == short:
            point.append(i)
        elif d < short:
            for j, k in g[i]:
                if d+2*k > short:
                    if d+2*k+2*dist_t[j] == 2*short:
                        path.append((i, j))

    for i in point:
        ans = (ans-dp_s[i]*dp_t[i]) % mod
    for i, j in path:
        ans = (ans-dp_s[i]*dp_t[j]) % mod

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    s, t = map(lambda x: int(x)-1, input().split())
    uvd = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append((b-1, c)) for a, b, c in uvd]
    [g[b-1].append((a-1, c)) for a, b, c in uvd]

    import heapq
    inf = 10**16
    mod = 10**9+7

    dist_s = [inf]*n
    dp_s = ([0]*n)+[1]
    h = [(0, s, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_s[i] == inf:
            dist_s[i] = d
            dp_s[i] = dp_s[a]
            for j, k in g[i]:
                if dist_s[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_s[i] == d:
            dp_s[i] = (dp_s[i]+dp_s[a]) % mod

    dist_t = [inf]*n
    dp_t = ([0]*n)+[1]
    h = [(0, t, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_t[i] == inf:
            dist_t[i] = d
            dp_t[i] = dp_t[a]
            for j, k in g[i]:
                if dist_t[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_t[i] == d:
            dp_t[i] = (dp_t[i]+dp_t[a]) % mod

    ans = dp_s[t]**2 % mod
    short = dist_s[t]

    point = []
    path = []

    for i in range(n):
        d = dist_s[i]*2
        if d == short:
            point.append(i)
        elif d < short:
            for j, k in g[i]:
                if d+2*k > short:
                    if d+2*k+2*dist_t[j] == 2*short:
                        path.append((i, j))

    for i in point:
        ans = (ans-dp_s[i]*dp_t[i]) % mod
    for i, j in path:
        ans = (ans-dp_s[i]*dp_t[j]) % mod

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    s, t = map(lambda x: int(x)-1, input().split())
    uvd = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append((b-1, c)) for a, b, c in uvd]
    [g[b-1].append((a-1, c)) for a, b, c in uvd]

    import heapq
    inf = 10**15
    mod = 10**9+7

    dist_s = [inf]*n
    dp_s = ([0]*n)+[1]
    h = [(0, s, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_s[i] == inf:
            dist_s[i] = d
            dp_s[i] = dp_s[a]
            for j, k in g[i]:
                if dist_s[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_s[i] == d:
            dp_s[i] = (dp_s[i]+dp_s[a]) % mod
    dp_s.pop()

    dist_t = [inf]*n
    dp_t = ([0]*n)+[1]
    h = [(0, t, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if dist_t[i] == inf:
            dist_t[i] = d
            dp_t[i] = dp_t[a]
            for j, k in g[i]:
                if dist_t[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif dist_t[i] == d:
            dp_t[i] = (dp_t[i]+dp_t[a]) % mod
    dp_t.pop()

    ans = dp_s[t]**2 % mod
    short = dist_s[t]

    for i in range(n):
        d = dist_s[i]*2
        if d == short:
            ans = (ans-dp_s[i]*dp_t[i]) % mod
        elif d < short:
            for j, k in g[i]:
                if d+2*k > short:
                    if d+2*k+2*dist_t[j] == 2*short:
                        ans = (ans-dp_s[i]*dp_t[j]) % mod

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq

mod = 10**9 + 7

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def dijkstra(G, s, t=None):
    dist = [-1]*len(G)
    fr = [0]*len(G)
    dist[s] = 0
    fr[s] = 1
    q = [(0, s)]
    while q:
        d, v = hq.heappop(q)
        if d > dist[v]: continue
        for x, c in G[v]:
            if dist[x] < 0 or dist[x] > d + c:
                dist[x] = d + c
                fr[x] = fr[v]
                hq.heappush(q, (d + c, x))
            elif dist[x] == d + c:
                fr[x] = (fr[x] + fr[v]) % mod
    return dist, fr


def solve():
  n, m = nm()
  s, t = nm()
  s -= 1; t -= 1
  G = [list() for _ in range(n)]
  for _ in range(m):
    u, v, d = nm()
    u -= 1; v -= 1
    G[u].append((v, d))
    G[v].append((u, d))
  diss, frs = dijkstra(G, s)
  dist, frt = dijkstra(G, t)
  cnt = frt[s] * frs[t] % mod
  for i in range(n):
    if diss[i] + dist[i] == dist[s] and diss[i] == dist[i]:
      # print(i)
      cnt = (cnt - (frs[i] * frt[i] % mod)**2 % mod) % mod
    for j, _ in G[i]:
      if diss[i] + dist[i] == dist[s] and diss[j] + dist[j] == dist[s] and \
      diss[i] < dist[i] and diss[j] > dist[j]:
        # print(i, j, (diss[i], diss[j]), (dist[i], dist[j]))
        cnt = (cnt - (frs[i] * frt[j] % mod)**2 % mod) % mod
  print(cnt)
  return

solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**10+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    dx,x = hq.heappop(q)
    k = dist[x][1]
    for y,d in graph[x]:
      if dist[y][0] > dx+d:
        dist[y][0] = dx+d
        dist[y][1] = k
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dx+d:
        dist[y][1] = (dist[y][1]+k)%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
#隣接リスト
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
#dst: S-T間の距離
#anslsに「2人が出会いうる辺/頂点を通るパスの本数」を格納
ans = dists[t][1]**2%mod
for v in range(1,n+1):
  if dists[v][0]+distt[v][0] != dst:
    continue
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ans = (ans-(dists[v][1]*distt[v][1])**2)%mod
  else:
    for u,d in graph[v]:
      if dists[u][0]*2 < dst and distt[v][0]*2 < dst:
        if dists[u][0]+distt[v][0]+d == dst:
          ans = (ans-(dists[u][1]*distt[v][1])**2)%mod
#答え: anslsの要素をaiとすると
#(Σai)^2-Σ(ai^2)になるはず…

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
#隣接リスト
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
#dst: S-T間の距離
#anslsに「2人が出会いうる辺/頂点を通るパスの本数」を格納
ans = (dst**2)%mod
for v in range(1,n+1):
  if dists[v][0]+distt[v][0] != dst:
    continue
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ans = (ans-(dists[v][1]*distt[v][1])**2)%mod
  else:
    for u,d in graph[v]:
      if dists[u][0]*2 < dst and distt[v][0]*2 < dst:
        if dists[u][0]+distt[v][0]+d == dst:
          ans = (ans-(dists[u][1]*distt[v][1])**2)%mod
#答え: anslsの要素をaiとすると
#(Σai)^2-Σ(ai^2)になるはず…

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
#隣接リスト
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
#dst: S-T間の距離
ansls = []
#anslsに「2人が出会いうる辺/頂点を通るパスの本数」を格納
for v in range(1,n+1):
  if dists[v][0]+distt[v][0] != dst:
    continue
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append((dists[v][1]*distt[v][1])%mod)
  else:
    for u,d in graph[v]:
      if dists[u][0]*2 < dst and distt[v][0]*2 < dst:
        if dists[u][0]+distt[v][0]+d == dst:
          ansls.append((dists[u][1]*distt[v][1])%mod)
#答え: anslsの要素をaiとすると
#(Σai)^2-Σ(ai^2)になるはず…
sm = sum(ansls)%mod
ans = (sm**2)%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
#隣接リスト
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
#dst: S-T間の距離
ansls = []
#anslsに「2人が出会いうる辺/頂点を通るパスの本数」を格納
for v in range(1,n+1):
  if dists[v]+distt[v] != dst:
    continue
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append((dists[v][1]*distt[v][1])%mod)
  else:
    for u,d in graph[v]:
      if dists[u][0]*2 < dst and distt[v][0]*2 < dst:
        if dists[u][0]+distt[v][0]+d == dst:
          ansls.append((dists[u][1]*distt[v][1])%mod)

#答え: anslsの要素をaiとすると
#(Σai)^2-Σ(ai^2)になるはず…
sm = sum(ansls)%mod
ans = (sm**2)%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
#隣接リスト
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
#S,Tからdijkstra
#distX[i]: [Xからiへの最短経路長、そのパスの本数]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
#dst: S-T間の距離
ansls = []
#anslsに「2人が出会う辺/頂点を通るパスの本数」を格納
for u,v,d in abd:
  #辺を全探索
  #sからaの距離 < dst/2 かつ tからbの距離 < dst/2 かつ
  #sからaの距離 + tからbの距離+辺の長さ == dstならその辺で出会う可能性がある
  for a,b in (u,v),(v,u):
    if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
      if dists[a][0]+distt[b][0]+d == dst:
        ansls.append((dists[a][1]*distt[b][1])%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append((dists[v][1]*distt[v][1])%mod)
sm = sum(ansls)%mod
ans = (sm**2)%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
if dists[t][0] != distt[s][0]:
  print(2/0)
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**10+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
        """
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
    """
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
if dst == 10**18:
  print(2/0)
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
import heapq as hq
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for a,b,d in abd:
  if dists[a][0] < distt[a][0]:
    if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
      if dists[a][0]+distt[b][0]+d == dst:
        ansls.append(dists[a][1]*distt[b][1]%mod)
  else:
    if dists[b][0]*2 < dst and distt[a][0]*2 < dst:
      if dists[b][0]+distt[a][0]+d == dst:
        ansls.append(dists[b][1]*distt[a][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s,t = map(int,input().split())
abd = [list(map(int,input().split())) for i in range(m)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
import heapq as hq
dists = [[10**18,0] for i in range(n+1)]
distt = [[10**18,0] for i in range(n+1)]
for start,dist in (s,dists),(t,distt):
  dist[start] = [0,1]
  q = [(0,start)]
  hq.heapify(q)
  while q:
    _,x = hq.heappop(q)
    for y,d in graph[x]:
      if dist[y][0] > dist[x][0]+d:
        dist[y][0] = dist[x][0]+d
        dist[y][1] = dist[x][1]
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dist[x][0]+d:
        dist[y][1] = (dist[y][1]+dist[x][1])%mod
dst = dists[t][0]
ansls = []
for a,b,d in abd:
  if dists[a][0] < distt[a][0]:
    if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
      if dists[a][0]+distt[b][0]+d == dst:
        ansls.append(dists[a][1]*distt[b][1]%mod)
  else:
    if dists[b][0]*2 < dst and distt[a][0]*2 < dst:
      if dists[b][0]+distt[a][0]+d == dst:
        ansls.append(dists[b][1]*distt[a][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
ans = (sum(ansls)%mod)**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
mod=10**9+7

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))

    def edge(self,_from):
        return self.G[_from]

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        cnt=[0]*self.V
        cnt[s]=1
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
                    cnt[e.to]=cnt[v]%mod
                elif d[e.to]==d[v]+e.cost:
                    cnt[e.to]+=cnt[v]
                    cnt[e.to]%=mod
        return d,cnt

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
S,T=map(int,input().split())
mati=Dijkstra(N)
for i in range(M):
    u,v,d=map(int,input().split())
    mati.add(u-1,v-1,d)
    mati.add(v-1,u-1,d)

spath,Sways=mati.shortest_path(S-1)
tpath,Tways=mati.shortest_path(T-1)

Submission status: Wrong Answer

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N,M=map(int,input().split())
S,T=map(int,input().split())
mati=Dijkstra(N)
edge=[[] for i in range(N)]
Edge=[]
for i in range(M):
    u,v,d=map(int,input().split())
    mati.add(u-1,v-1,d)
    mati.add(v-1,u-1,d)
    edge[u-1].append((v-1,d))
    edge[v-1].append((u-1,d))
    Edge.append((u-1,v-1,d))
    Edge.append((v-1,u-1,d))