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: Time Limit Exceeded

Solution code:
import scipy.sparse as sps
import scipy.sparse.csgraph as spsc
import numpy as np
from time import process_time as timer

N,M = map(int,input().split())

S,T = map(int,input().split())
S,T = S-1,T-1

E = sps.dok_matrix((N,N),dtype=int)

def it():
  for _ in range(M):
    u,v,d = map(int,input().split())
    u,v = u-1,v-1
    yield ((u,v),d)
E.update(it())


dS,dT = spsc.dijkstra(E,directed=False, indices=[S,T]).astype(int)
D = dS[T]
D2 = D//2

E = tuple((u,v) for d,u,v in ((d,u,v) if dS[u] <= dS[v] else (d,v,u) for (u,v),d in E.items()) if dS[u]+d+dT[v] == D)

MOD = 10**9+7


def helper(start, edges):
  cnts = [0]*N
  cnts[start] = 1
  for d,u,v in edges:
    cnts[v] = (cnts[v] + cnts[u]) % MOD
  return cnts


Sn = helper(S,sorted((dS[u],u,v) for u,v in E))
Tn = helper(T,sorted((dT[v],v,u) for u,v in E))

from functools import reduce

def it():
  for v in range(N):
    if dS[v] == D2:
      yield (Sn[v]*Tn[v])**2

c0 = reduce(lambda x,y: (x+y)%MOD, it(), 0) if D%2==0 else 0

diff = dS-dT

def it():
  for u,v in E:
    if diff[u] < 0 < diff[v]:
      yield (Sn[u]*Tn[v])**2

c1 = reduce(lambda x,y: (x+y)%MOD, it(), 0)

total = Sn[T]*Tn[S]
cnt = c0+c1

print((total-cnt)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import scipy.sparse as sps
import scipy.sparse.csgraph as spsc
import numpy as np

N,M = map(int,input().split())

S,T = map(int,input().split())
S,T = S-1,T-1

E = sps.dok_matrix((N,N),dtype=int)

adj = list(list() for _ in range(N))

def it():
  for _ in range(M):
    u,v,d = map(int,input().split())
    u,v = u-1,v-1
    adj[u].append((v,d))
    adj[v].append((u,d))
    yield ((u,v),d)
    yield ((v,u),d)
E.update(it())

dS,dT = spsc.dijkstra(E,directed=False, indices=[S,T])
D = dS[T]

V = dS+dT == D
MOD = 10**9+7

def helper(start, dist):
  import heapq as hq
  cnts = [0]*N
  cnts[start] = 1

  edges = []
  for u in range(N):
    if V[u]:
      for v,d in adj[u]:
        if V[v] and dist[v]-dist[u] == d:
          edges.append((dist[u],u,v))

  edges.sort()

  for _,u,v in edges:
    cnts[v] += cnts[u]
    cnts[v] %= MOD

  return cnts


Sn = helper(S,dS)
Tn = helper(T,dT)


c0 = 0
c1 = 0

for v in range(N):
  if V[v]:
    dv = dS[v]

    if dv*2 == D:
      c0 += Sn[v]*Tn[v]
      c0 %= MOD

    elif dv*2 < D:
      for u,d in adj[v]:
        du = dS[u]
        if V[u] and du*2 > D and du-dv == d:
          c1 += Sn[v]*Tn[u]
          c1 %= MOD

total = Sn[T]*Tn[S]
cnt = c0+c1

print((total-cnt)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import heapq
MOD = 10 ** 9 + 7

N, M = map(int, input().split())
S, T = map(lambda x: int(x) - 1, input().split())

adjList = [[] for i in range(N)]
for i in range(M):
    U, V, D = map(int, input().split())
    adjList[U - 1].append((V - 1, D))
    adjList[V - 1].append((U - 1, D))

# 頂点Sから各頂点への最短路の個数
numRouteS = [0 for i in range(N)]
numRouteS[S] = 1

cost = [float('inf')] * N
cost[S] = 0
prev = [None] * N

pq = []
heapq.heappush(pq, (0, S))

vs = []
while pq:
    c, vNow = heapq.heappop(pq)
    if c > cost[vNow]: continue
    if c > cost[T]: break
    vs += [vNow]

    for v2, wt in adjList[vNow]:
        c2 = cost[vNow] + wt
        if c2 <= cost[v2]:
            if c2 == cost[v2]:
                prev[v2] += [vNow]
                numRouteS[v2] = (numRouteS[v2] + numRouteS[vNow]) % MOD
            else:
                cost[v2] = c2
                prev[v2] = [vNow]
                numRouteS[v2] = numRouteS[vNow]
                heapq.heappush(pq, (c2, v2))

# 頂点Tから各頂点への最短路の個数
numRouteT = [0] * N
numRouteT[T] = 1
for v in reversed(vs[1:]):
    for v0 in prev[v]:
        numRouteT[v0] = (numRouteT[v0] + numRouteT[v]) % MOD

# 二人の最短路の選び方の組から、途中で出会うものを引く
cST = cost[T]
ans = (numRouteS[T] ** 2) % MOD

for v, c in enumerate(cost):
    if c * 2 == cST:
        x = (numRouteS[v] ** 2) % MOD
        y = (numRouteT[v] ** 2) % MOD
        ans = (ans - x * y) % MOD

for v, c in enumerate(cost):
    if c * 2 < cST:
        for v2, wt in adjList[v]:
            if (cost[v2] * 2 > cST) and c + wt == cost[v2]:
                x = (numRouteS[v] ** 2) % MOD
                y = (numRouteT[v2] ** 2) % MOD
                ans = (ans - x * y) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = defaultdict(set)
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def backward_search(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] ** 2 * patterns_b[d] ** 2
            collision %= 1000000007
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = backward_search(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return (pow(pt, 2, 1000000007) - collision) % 1000000007


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            collision %= 1000000007
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return (pow(pt, 2, 1000000007) - collision) % 1000000007


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[t] < cost:
            break
        if visited[v] < cost:
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if visited[t] < cost:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if v == t:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = deque([(t, -1)])
    while q:
        v, d = q.popleft()
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        q.extend((a, v) for a in ancestors[v])
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
from heapq import heappush, heappop

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)
INF = 10**16
MOD = 10**9 + 7

(N, M) = reads()
(S, T) = reads()
(S, T) = (S-1, T-1)

edges = [[] for _ in range(N)]
for _ in range(M):
    (U, V, D) = reads()
    (U, V) = (U-1, V-1)
    edges[U].append((D, V))
    edges[V].append((D, U))

def dijkstra(s):
    que = [(0, s)]
    ds = [INF] * N; ds[s] = 0

    while que:
        (D, v) = heappop(que)
        if ds[v] < D:
            continue
        for (d, w) in edges[v]:
            if ds[w] > ds[v] + d:
                ds[w] = ds[v] + d
                heappush(que, (ds[w], w))
    return ds

def counting(s, ds):
    ns = [0] * N; ns[s] = 1
    visited = [False] * N
    
    def walk(i):
        if visited[i]:
            return
        visited[i] = True
        for (d, w) in edges[i]:
            if ds[w] - ds[i] == d:
                ns[w] = (ns[w] + ns[i]) % MOD
                walk(w)

    walk(s)
    return ns

dS = dijkstra(S)
nS = counting(S, dS)

dT = dijkstra(T)
nT = counting(T, dT)

dtot = dS[T]
ans = (nS[T] * nT[S]) % MOD

for i in range(N):
    if dS[i] == dT[i] and dS[i] + dT[i] == dtot:
        diff = (nS[i] * nT[i]) % MOD
        ans = (ans - diff) % MOD

egen = ((i, j, d) for i in range(N) for (d, j) in edges[i] if i < j)
for i, j, d in egen:
    if dS[i] + d + dT[j] == dtot and abs(dT[j] - dS[i]) < d:
        n1 = (nS[i] * nT[j]) % MOD
        n2 = (n1 * n1) % MOD
        ans = (ans - n2) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush


def ex_dijkstra(s, t, links):
    q = [(0, s, -1)]
    visited = [float('inf')] * n
    ancestors = [set() for _ in range(n)]
    patterns = [0] * (n + 1)
    patterns[-1] = 1
    while q:
        cost, v, a = heappop(q)
        if visited[v] < cost:
            if v == t:
                break
            continue
        visited[v] = cost
        ancestors[v].add(a)
        patterns[v] += patterns[a]
        for du, u in links[v]:
            nc = cost + du
            if visited[u] < nc:
                continue
            heappush(q, (nc, u, v))
    return visited, ancestors, patterns


def reconstruct(t, time, visited, ancestors, patterns_f):
    collision = 0
    patterns_b = [0] * (n + 1)
    patterns_b[-1] = 1
    q = [(t, -1)]
    while q:
        v, d = heappop(q)
        if visited[v] < time:
            collision += patterns_f[v] * patterns_b[d]
            continue
        patterns_b[v] += patterns_b[d]
        for a in ancestors[v]:
            heappush(q, (a, v))
    return collision


def solve(s, t, links):
    visited, ancestors, patterns = ex_dijkstra(s, t, links)
    # print(visited, ancestors, patterns)
    collision = reconstruct(t, visited[t] / 2, visited, ancestors, patterns)
    pt = patterns[t]
    return pt ** 2 - collision


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [set() for _ in range(n)]
for _ in range(m):
    u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((d, v))
    links[v].add((d, u))
print(solve(s, t, links))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

def dijkstra(s):
    hq=[(0,s)]
    dist=[INF]*n
    dp=[0]*n
    dp[s]=1
    dist[s]=0
    checked=[0]*n
    while hq:
        min_dist,u=heappop(hq)
        if checked[u]:
            continue
        checked[u]=1
        for v,c in G[u]:
            if dist[u]+c<dist[v]:
                dist[v]=dist[u]+c
                dp[v]=dp[u]
                heappush(hq,(dist[v],v))
            elif dist[u]+c==dist[v]:
                dp[v]+=dp[u]
                dp[v]%=mod
    return dp, dist

n, m = LI()
s, t = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a,b, d = LI()
    G[a - 1] += [(b - 1, d)]
    G[b - 1] += [(a - 1, d)]

dp1,dist1=dijkstra(s-1)
dp2,dist2=dijkstra(t-1)
total=dist1[t-1]
ans=dp1[t-1]*dp2[s-1]%mod
for i in range(n):
    if dist1[i]==dist2[i]==total/2:
        ans-=pow(dp1[i]*dp2[i]%mod,2,mod)

for j in range(n):
    for k, ci in G[j]:
        if dist1[j]+dist2[k]+ci==total and dist1[j]<total/2 and dist2[k]<total/2:
            ans-=pow(dp1[j]*dp2[k]%mod,2,mod)

print(ans%mod)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()
S,T = MI()
edges = [[] for _ in range(N+1)]
edges2 = []
for _ in range(M):
    U,V,D = MI()
    edges[U].append((V,D))
    edges[V].append((U,D))
    edges2.append((U,V,D))
    edges2.append((V,U,D))

mod = 10**9+7

from heapq import heappop,heappush

distS = [(10**18,0)]*(N+1)  # (最短距離,経路数)
distS[S] = (0,1)
qS = []
heappush(qS,(0,S))
vS = [False]*(N+1)
while qS:
    d,i = heappop(qS)
    if vS[i]:
        continue
    vS[i] = True
    for j,d in edges[i]:
        if vS[j]:
            continue
        if distS[j][0] > distS[i][0] + d:
            distS[j] = (distS[i][0] + d,distS[i][1])
            heappush(qS,(distS[i][0] + d,j))
        elif distS[j][0] == distS[i][0] + d:
            distS[j] = (distS[j][0],distS[j][1]+distS[i][1])
            heappush(qS,(distS[i][0] + d,j))

distT = [(10**18,0)]*(N+1)
distT[T] = (0,1)
qT = []
heappush(qT,(0,T))
vT = [False]*(N+1)
while qT:
    d,i = heappop(qT)
    if vT[i]:
        continue
    vT[i] = True
    for j,d in edges[i]:
        if vT[j]:
            continue
        if distT[j][0] > distT[i][0] + d:
            distT[j] = (distT[i][0] + d,distT[i][1])
            heappush(qT,(distT[i][0] + d,j))
        elif distT[j][0] == distT[i][0] + d:
            distT[j] = (distT[j][0],distT[j][1]+distT[i][1])
            heappush(qT,(distT[i][0] + d,j))

a,b = distS[T]  # SからTまでの最短距離,経路数
ans = b**2 % mod

# 頂点で出くわす場合
if a % 2 == 0:
    for i in range(1,N+1):
        if distS[i][0] == distT[i][0] == a//2:
            ans -= (distS[i][1]*distT[i][1])**2
            ans %= mod

# 辺上で出くわす場合
for i in range(2*M):
    U,V,D = edges2[i]
    if distS[U][0] < (a+1)//2 and distT[V][0] < (a+1)//2 and a == distS[U][0] + D + distT[V][0]:
        ans -= (distS[U][1]*distT[V][1])**2
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

from heapq import *

def solve():
    dist = [inf] * n
    cnt = [0] * n
    hp = []
    heappush(hp, (0, s))
    dist[s] = 0
    cnt[s] = 1
    while hp:
        d, u = heappop(hp)
        if d > dist[t]: break
        if d > dist[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == dist[v]: cnt[v] += cnt[u]
            elif nd < dist[v]:
                dist[v] = nd
                cnt[v] = cnt[u]
                heappush(hp, (nd, v))

    distr = [inf] * n
    cntr = [0] * n
    hp = []
    heappush(hp, (0, t))
    distr[t] = 0
    cntr[t] = 1
    while hp:
        d, u = heappop(hp)
        #print(d,u,hp,distr,cntr)
        if d * 2 > dist[t]: continue
        if d > distr[u]: continue
        for v, c in to[u]:
            nd = d + c
            if nd == distr[v]: cntr[v] += cntr[u]
            elif nd < distr[v]:
                distr[v] = nd
                cntr[v] = cntr[u]
                heappush(hp, (nd, v))

    ans = pow(cnt[t], 2, md)
    dt = dist[t]
    for u in range(n):
        if dist[u] * 2 == dt:
            ans -= (cnt[u] * cntr[u])**2
            ans %= md
    for u, v, c in uvd:
        for _ in range(2):
            if dist[u] + distr[v] + c == dt and dist[u] * 2 < dt and distr[v] * 2 < dt:
                ans -= (cnt[u] * cntr[v])**2
                ans %= md
            u, v = v, u
    print(ans)

md = 10 ** 9 + 7
inf = 10 ** 16
n, m = MI()
s, t = MI1()
to = [[] for _ in range(n)]
uvd = []
for _ in range(m):
    u, v, d = MI()
    to[u - 1].append((v - 1, d))
    to[v - 1].append((u - 1, d))
    uvd.append((u - 1, v - 1, d))

solve()

Submission status: Accepted

Solution code:
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    def dijkstra(edges, start=0):
        dist = [inf] * len(edges)
        dist[start] = 0
        Q = [(0, start)]  # (dist,vertex)
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  # 候補として挙がったd,vだが、他に短いのがある
            for u, cost in edges[v]:
                if dist[u] > dist[v] + cost:
                    dist[u] = dist[v] + cost
                    heapq.heappush(Q, (dist[u], u))
        return dist
    N, M = LI()
    S, T = LI()
    S -= 1; T -= 1
    V = [set()for _ in range(N)]
    for _ in range(M):
        u, v, c = LI()
        u -= 1; v -= 1
        V[u].add((v,c))
        V[v].add((u,c))
    distS = dijkstra(V,S)
    distT = dijkstra(V,T)
    L = distS[T]
    numS = [i for i in range(N)]
    C = list(zip(distS,numS))
    C.sort()
    _, numS = zip(*C)
    numT = [i for i in range(N)]
    C = list(zip(distT,numT))
    C.sort()
    _, numT = zip(*C)
    #print(numS)

    dp1 = [0]*N
    dp2 = [0]*N
    dp1[S] = 1; dp2[T] = 1
    S_collision_points = set()
    S_collision_edges = set()
    for now in numS:
        if distS[now] + distT[now] == L and distS[now] == distT[now]:
            S_collision_points.add(now)
        #print(now,used,dp1)
        for v,c in V[now]:
            if distT[v]+distS[now]==L-c:
                #print(distS[v],distS[now],now)
                dp1[v] += dp1[now]
                dp1[v] %= mod
                if distS[now]*2<L and L<distS[v]*2:
                    S_collision_edges.add((now,v))
    for now in numT:
        for v,c in V[now]:
            if distS[v]+distT[now]==L-c:
                dp2[v] += dp2[now]
                dp2[v] %= mod
    collision_points = S_collision_points
    collision_edges = S_collision_edges
    #print(distS)
    #print(distT)
    #print(dp1)
    #print(dp2)
    #print(S_collision_edges)
    ans = 0
    ans += dp1[T]**2
    ans %= mod
    for p in collision_points:
        if distS[p]==distT[p]:
            ans -= (dp1[p]**2)*(dp2[p]**2)
            ans += supermod
            ans %= mod
            #print(ans,p)
    for u,v in collision_edges:
        ans -= (dp1[u]**2)*(dp2[v]**2)
        ans += supermod
        ans %= mod
        #print(ans,u,v)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
supermod = mod**4
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.buffer.readline

def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    計算量: O((E+V)logV)
    """
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    n = len(graph)
    dist = [INF] * n
    ptn = [0] * n 
    dist[start] = 0
    ptn[start] = 1 
    q = [(0, start)] # q = [(startからの距離, 現在地)]
    while q:
        d, v = heapq.heappop(q)
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            if dist[v] + cost == dist[nxt_v]:
                ptn[nxt_v] += ptn[v]
                ptn[nxt_v] %= MOD
            if dist[v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[v] + cost
                ptn[nxt_v] = ptn[v]
                ptn[nxt_v] %= MOD
                heapq.heappush(q, (dist[nxt_v], nxt_v))
    return dist, ptn




n, m = list(map(int, input().split()))
s, t = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
MOD = 10 ** 9 + 7

s -= 1
t -= 1
graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
dist_st, ptn_st = dijkstra(s, graph)
dist_ts, ptn_ts = dijkstra(t, graph)

min_cost, max_ptn = dist_st[t], ptn_st[t]
all_ptn = (max_ptn * max_ptn) % MOD

# 最短路で使用する頂点を復元
use = [False] * n
use[t] = True
stack = [t]
while stack:
    v = stack.pop()
    for prv_v, cost in graph[v]:
        if use[prv_v]:
            continue
        if dist_st[v] == dist_st[prv_v] + cost:
            use[prv_v] = True
            stack.append(prv_v)

# 頂点上で出会うとき
for i in range(n):
    if dist_st[i] == dist_ts[i] and use[i]:
        all_ptn -= (ptn_st[i] * ptn_ts[i]) ** 2
        all_ptn %= MOD
        
# 辺上で出会うとき
for a, b, cost in info:
    a -= 1
    b -= 1
    if abs(dist_st[a] - dist_st[b]) != cost:
        continue
    if (not use[a]) or (not use[b]):
        continue
    if dist_st[a] > dist_st[b]:    
        a, b = b, a
    if dist_st[a] < dist_ts[a] and dist_st[b] > dist_ts[b]:
        all_ptn -= (ptn_st[a] * ptn_ts[b]) ** 2
    all_ptn %= MOD
print(all_ptn)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, m = map(int, input().split())
    s, t = map(lambda x: int(x)-1, input().split())
    g = [[] for _ in [0]*n]
    for i in range(m):
        a, b, c = map(int, input().split())
        g[a-1].append((b-1, c))
        g[b-1].append((a-1, c))

    import heapq
    inf = 10**16
    short = inf
    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 d > short:
            break
        elif i == t:
            short = d
        d2 = dist_s[i]
        if d2 == 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 d2 == 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 d > short:
            break
        d2 = dist_t[i]
        if d2 == 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 d2 == d:
            dp_t[i] = (dp_t[i]+dp_t[a]) % mod

    ans = dp_s[t]**2 % mod

    for i, (p, q) in enumerate(zip(dist_s, dist_t)):
        if p+q == short:
            d = p*2
            if d == short and q*2 == short:
                ans = (ans-(dp_s[i]*dp_t[i])**2) % 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])**2) % mod

    print(ans)


main()