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

Solution (Python):
from heapq import heappop, heappush
import sys

MOD, INF = 1000000007, float('inf')


def count_routes(visited, s, links):
    counts = [0] * n
    counts[s] = 1
    for dv, v in sorted((d, v) for v, d in enumerate(visited) if d != INF):
        for u, du in links[v].items():
            if dv + du == visited[u]:
                counts[u] += counts[v]
                counts[u] %= MOD
    return counts


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    collision_nodes, collision_links = set(), set()
    limit = 0
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if is_bwd:
            visited_self = visited_bwd
            visited_opp = visited_fwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd

        relax_flag = False
        cost_preceding = visited_self[v]
        if cost_preceding == INF:
            visited_self[v] = cost
            relax_flag = True
        elif cost > cost_preceding:
            continue

        cost_opp = visited_opp[v]
        if cost_opp != INF:
            limit = cost + cost_opp
            if cost == cost_opp:
                collision_nodes.add(v)
            else:
                collision_links.add((v, a) if is_bwd else (a, v))
            break

        if relax_flag:
            for u, du in links[v].items():
                nc = cost + du
                if visited_self[u] < nc:
                    continue
                heappush(q, (nc, cost, u, v, is_bwd))

    collision_time = limit / 2
    while q:
        cost, cost_a, v, a, is_bwd = heappop(q)
        if cost > limit:
            break
        visited_self = visited_bwd if is_bwd else visited_fwd
        if visited_self[v] == INF:
            visited_self[v] = cost
        if is_bwd:
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
        else:
            collision_links.add((v, a) if is_bwd else (a, v))

    counts_fwd = count_routes(visited_fwd, s, links)
    counts_bwd = count_routes(visited_bwd, t, links)
    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = counts_fwd[v] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    for u, v in collision_links:
        if visited_fwd[u] + visited_bwd[v] + links[u][v] == limit:
            r = counts_fwd[u] * counts_bwd[v]
            shortest_count += r
            shortest_count %= MOD
            collision_count += r * r
            collision_count %= MOD

    return (shortest_count ** 2 - collision_count) % MOD


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
links = [{} for _ in range(n)]
for uvd in sys.stdin.readlines():
    u, v, d = map(int, uvd.split())
    
    
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Solution (Python):
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = map(int,stdin.readline().split())
S,T = map(int,stdin.readline().split())
S,T = S-1,T-1

inf = float('inf')
 
E = [[] for _ in range(N)]
lines = stdin.readlines()
for line in lines:
  u,v,d = map(int,line.split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [inf]*N
dT = [inf]*N
 
Q = [(0,S,False),(0,T,True)]

D = inf

 
while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break

  dM = dT if f else dS
  dN = dS if f else dT
  if dM[v] > d:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] > d and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
   
  D = min(dN[v]+d,D)
 
del Q


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

  for d,v in sorted((d,v) for v,d in enumerate(dist) if d != inf):
    c = cnts[v]
    for u,dd in E[v]:
      if dd+d == dist[u]:
        cnts[u] = (cnts[u]+c) % MOD

  return cnts

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


def it():
  for v in range(N):
    if dS[v] != inf:
      ds = dS[v]
      if dT[v] == ds and ds*2 == D:
        yield Sn[v]*Tn[v] % MOD
      else:
        for u,d in E[v]:
          if abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = tuple(it())
 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X),0)

print((total-sub)%MOD)

Solution (Python):
from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = map(int,stdin.readline().split())
S,T = map(int,stdin.readline().split())
S,T = S-1,T-1
 
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
  u,v,d = map(int,line.split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [None]*N
dT = [None]*N
 
Q = [(0,S,False),(0,T,True)]
 
D = float('inf')
 
 
while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break

  dM = dT if f else dS
  dN = dS if f else dT
  if dM[v] is None:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] is None and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
 
  if dN[v] is not None:
    D = min(dN[v]+d,D)
 
del Q

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

  for d,v in sorted((d,v) for v,d in enumerate(dist) if d is not None):
    c = cnts[v]
    for u,dd in E[v]:
      if dd+d == dist[u]:
        cnts[u] = (cnts[u]+c) % MOD

  return cnts

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


def it():
  for v in range(N):
    if dS[v] is not None:
      ds = dS[v]
      if dT[v] == ds and ds*2 == D:
        yield Sn[v]*Tn[v] % MOD
      else:
        for u,d in E[v]:
          if dT[u] is not None and abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = list(it())

 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X),0)
print((total-sub)%MOD)

Solution (Python):
from heapq import heappop, heappush
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))


numRouteS = [0] * N
numRouteS[S] = 1

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

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

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


numRouteT = [0] * N
numRouteT[T] = 1
cST = cost[T]
for iV, v in enumerate(reversed(vs)):
    if cost[v] * 2 < cST:
        iVLim = len(vs) - iV
        break
    for v0 in prev[v]:
        numRouteT[v0] = (numRouteT[v0] + numRouteT[v]) % MOD


ans = (numRouteS[T] ** 2) % MOD

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

for v in vs[iVLim:]:
    if cost[v] * 2 > cST: break
    x = (numRouteS[v] ** 2) % MOD
    y = (numRouteT[v] ** 2) % MOD
    ans = (ans - x * y) % MOD

print(ans)

Solution (Python):
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))


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))


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)