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

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

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

Solution (Python):
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)]  
        while (Q):
            d, v = heapq.heappop(Q)
            if dist[v] < d: continue  
            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)
    

    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)
        
        for v,c in V[now]:
            if distT[v]+distS[now]==L-c:
                
                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
    
    
    
    
    
    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
            
    for u,v in collision_edges:
        ans -= (dp1[u]**2)*(dp2[v]**2)
        ans += supermod
        ans %= mod
        
    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
"""

Solution (Python):
import heapq
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 10**9+7
class DijkstraList():
	
	
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [float("inf") for _ in range(self.size)]
		self.dist[self.start] = 0
		self.dp = [0 for _ in range(self.size)]
		self.dp[self.start] = 1
		
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.dp[v] = self.dp[u]
					
					heapq.heappush(self.q, (self.dist[v], v))
				elif self.dist[v] == u_dist + w:
					self.dp[v] += self.dp[u]
					self.dp[v] %= MOD

			self.cnt += 1
		
		return

	def distance(self, goal):
		return self.dist[goal]

	def get_dp(self, x):
		return self.dp[x]

n, m = map(int, input().split())
s, t = map(int, input().split())
s, t = s-1, t-1
adj = [[] for _ in range(n)]
for _ in range(m):
	u, v, d = map(int, input().split())
	adj[u-1].append([v-1, d])
	adj[v-1].append([u-1, d])
S, T = DijkstraList(adj, s), DijkstraList(adj, t)
S.solve()
T.solve()
ans = pow(S.get_dp(t), 2, MOD)
goal = S.distance(t)


for i in range(n):
	SI, TI = S.distance(i), T.distance(i)
	if SI + TI != goal:
		continue
	if SI*2 == goal:
		ans -= S.get_dp(i) * T.get_dp(i) * S.get_dp(i) * T.get_dp(i)
		ans %= MOD

	else:
		for j, d in adj[i]:
			if i>j:
				continue
			SJ, TJ = S.distance(j), T.distance(j)
			if SJ + TJ != goal or abs(SI - SJ) != d:
				continue
			if SI*2 < goal < SJ*2:
				
				ans -= S.get_dp(i) * T.get_dp(j) * S.get_dp(i) * T.get_dp(j)
				ans %= MOD
			elif SJ*2 < goal < SI*2:
				
				ans -= S.get_dp(j) * T.get_dp(i) * S.get_dp(j) * T.get_dp(i)
				ans %= MOD

print(ans)

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

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

Solution (Python):
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]:
      
      cnt = (cnt - (frs[i] * frt[i] % mod)**2 % mod) % mod
    for j, x in G[i]:
      if diss[i] + x + dist[j] == dist[s] and diss[i] < dist[i] and diss[j] > dist[j]:
        
        cnt = (cnt - (frs[i] * frt[j] % mod)**2 % mod) % mod
  print(cnt)
  return

solve()

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

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


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



print(ans%mod)

Solution (Python):
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)]  
        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 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)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
                    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
sys.setrecursionlimit(1000000)

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)

ans=Sways[T-1]*Tways[S-1]
ans%=mod
for u in range(N):
    for e in mati.edge(u):
        v=e.to
        d=e.cost
        ans-=(Tways[v]*Sways[u])**2*(spath[u]+d+tpath[v]==spath[T-1] and spath[u]+d!=tpath[v] and spath[u]!=tpath[v]+d and (tpath[v]+d>=spath[u]>=tpath[v] or tpath[v]+d>=spath[u]+d>=tpath[v]))
        ans%=mod

for i in range(N):
    ans-=(Tways[i]*Sways[i])**2*(spath[i]+tpath[i]==spath[T-1] and spath[i]==tpath[i])
    ans%=mod

print(ans%mod)

Solution (Python):


def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    n, m = map(int, input().split())
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    from collections import defaultdict
    ns = defaultdict(set)
    for i in range(m):
        u, v, d = map(int, input().split())
        ns[u-1].add((v-1, d))
        ns[v-1].add((u-1, d))
    
    def _dijkstra(N, s, Edge):
        import heapq
        geta = 10**15
        inf = geta
        dist = [inf] * N
        dist[s] = 0
        Q = [(0, s)]
        dp = [0]*N
        dp[s] = 1
        while Q:
            dn, vn = heapq.heappop(Q)
            if dn > dist[vn]:
                continue
            for vf, df in Edge[vn]:
                if dist[vn] + df < dist[vf]:
                    dist[vf] = dist[vn] + df
                    dp[vf] = dp[vn]
                    heapq.heappush(Q, (dn + df,vf))
                elif dist[vn] + df == dist[vf]:
                    dp[vf] = (dp[vf] + dp[vn]) % M
        return dist, dp

    def dijkstra(start):
        import heapq
        vals = [None] * n
        nums = [None] * n
        nums[start] = 1
        h = [(0, start)] 
        vals[start] = 0
        while h:
            val, u = heapq.heappop(h)
            for v, d in ns[u]:
                if vals[v] is None or vals[v]>val+d:
                    vals[v] = val+d
                    nums[v] = nums[u]
                    heapq.heappush(h, (vals[v], v))
                elif vals[v] is not None and vals[v]==val+d:
                    nums[v] = (nums[v] + nums[u]) % M
        return vals, nums
    
    vals1, nums1 = dijkstra(s)
    vals2, nums2 = dijkstra(t)
    
    T = vals1[t]

    c1 = 0 
    c2 = 0 
    
    for u in range(n):
        if 2*vals1[u]==T and 2*vals2[u]==T:
            c1 = (c1 + pow((nums1[u] * nums2[u]), 2, M)) % M
        for v,d in ns[u]:
            if (vals1[u]+d+vals2[v]==T) and (2*vals1[u] < T < 2*(vals1[u] + d)):
                c2 = (c2 + (nums1[u] * nums2[v])**2) % M
    print((nums1[t]*nums2[s] - (c1+c2)) % M)
hoge()

Solution (Python):
import sys
input = sys.stdin.readline

INF = 10**18
mod = 10**9+7

import heapq as hp

N, M = map(int, input().split())
s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[] for _ in range(N)]
for _ in range(M):
    n, m, d = map(int, input().split())
    graph[n-1].append((d, m-1)) 
    graph[m-1].append((d, n-1)) 

def dijkstra(s):
    D = [INF for _ in range(N)] 
    B = [0]*N
    D[s] = 0
    B[s] = 1
    q = [] 
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q)
        if D[np] < nd:
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d:
                D[p] = D[np] + d
                B[p] = B[np]
                hp.heappush(q, (D[p], p))
            elif D[p] == D[np] + d:
                B[p] = (B[p] + B[np])%mod
    return D, B

sD, sB = dijkstra(s)
tD, tB = dijkstra(t)

distance = sD[t]

ans = 0
for n in range(N):
    for d, m in graph[n]:
        if sD[n] + d + tD[m] == distance and 2*sD[n] < distance < 2*(sD[n]+d):
            ans = (ans + (sB[n]*tB[m])**2)%mod
    if sD[n] + tD[n] == distance and 2*sD[n] == distance:
        ans = (ans + (sB[n]*tB[n])**2) % mod
ans = (sB[t]*tB[s] - ans) % mod
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = geta
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((d, v))
    Edge[v].append((d, u))
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for cost,vf in Edge[i]:
        if dists[i]+cost+distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)

Solution (Python):
import sys
from collections import deque, defaultdict
import heapq
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    collision_T = dist[t] / 2 if dist[t] % 2 == 1 else dist[t] // 2
    route = [0] * (N+1)
    route[t] = 1
    que = []
    heapq.heappush(que, (-dist[t], t))
    col_edge = set()
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.add((u, v))
                elif dist[v] == collision_T:
                    col_edge.add((v, v))
                if not seen[u]:
                    heapq.heappush(que, (-dist[u], u))
                    seen[u] = 1

    
    route2 = [0] * (N+1)
    route2[s] = 1
    que = []
    heapq.heappush(que, (0, s))
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    heapq.heappush(que, (dist[u], u))
                    seen[u] = 1

    
    

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = 10**18
mod = 10**9+7
def dijkstra(start, n, graph):
    route_cnt = [start] * n
    route_cnt[start] = 1
    que = [(0, start)]
    dist = [INF] * n
    dist[start] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for c, v in graph[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                route_cnt[v] = route_cnt[u]
                heappush(que, (dist[u] + c  , v))
            elif dist[u] + c == dist[v]:
                route_cnt[v] = (route_cnt[v] + route_cnt[u]) % mod
    return route_cnt, dist
N, M = map(int, input().split())
S, T = map(int, input().split())
G = [[] for _ in range(N)]
edges = []
for _ in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((d, v-1))
    G[v-1].append((d, u-1))
    edges.append((v-1, u-1, d))
num_s, dist_s = dijkstra(S-1, N, G)
num_t, dist_t = dijkstra(T-1, N, G)
ans = num_s[T-1]**2%mod
l = dist_s[T-1]
for u, v, d in edges:
    if dist_s[v]<dist_s[u]:
        u, v = v, u
    if dist_s[u]*2<l<dist_s[v]*2 and dist_s[u]+dist_t[v]+d == l:
        ans-=(num_s[u]**2%mod)*(num_t[v]**2%mod)
        ans%=mod
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=(num_t[v]**2%mod)*(num_s[v]**2%mod)
        ans%=mod
print(ans%mod)