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: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    s,t = LI()
    e = collections.defaultdict(list)
    for _ in range(m):
        u,v,d = LI()
        e[u].append((v,d))
        e[v].append((u,d))

    def search(s,t):
        d = collections.defaultdict(lambda: inf)
        dc = collections.defaultdict(int)
        d[s] = 0
        dc[s] = 1
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            dc[u] %= mod
            if u == t:
                return (d,dc)

            uc = dc[u]

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] < vd:
                    continue
                if d[uv] > vd:
                    d[uv] = vd
                    dc[uv] = uc
                    heapq.heappush(q, (vd, uv))
                elif d[uv] == vd:
                    dc[uv] += uc

        return (d,dc)

    d1,dc1 = search(s,t)
    d2,dc2 = search(t,s)
    rd = d1[t]
    kk = rd / 2.0

    r = dc1[t] ** 2 % mod
    for k in list(d1.keys()):
        t = d1[k]
        c = dc1[k]
        if t > kk:
            continue
        if t == kk:
            if d2[k] == t:
                r -= pow(c,2,mod) * pow(dc2[k],2,mod) % mod
            continue

        for uv, ud in e[k]:
            if d2[uv] >= kk or t + ud + d2[uv] != rd:
                continue
            r -= pow(c,2,mod) * pow(dc2[uv],2,mod) % mod

    return r % mod




print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
sys.setrecursionlimit(100000)
MOD = 10**9 + 7

def dijkstra(g, v_size, st):
    """Dijkstra method"""

    d = [float('inf')] * v_size
    d[st] = 0

    que = [(0, st)]     # (min_dist, vertex)
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue
        for v1, dist in g[v0]:
            if d[v1] > d[v0] + dist:
                d[v1] = d[v0] + dist
                heapq.heappush(que, (d[v1], v1))

    return d

def solve(f):
    n, m = f.read_int_list()
    s, t = f.read_int_list()
    g = collections.defaultdict(list)
    for m in xrange(m):
        u, v, d = f.read_int_list()
        g[u-1].append((v-1, d))
        g[v-1].append((u-1, d))

    d = dijkstra(g, n, s-1)

    cand = []
    for i in xrange(n):
        if d[t-1] == d[i]*2: cand.append((i,i))

    memo = [0]*n
    memo[t-1] = 1
    ary = [(d[i], i) for i in xrange(n)]
    ary.sort(reverse=True)

    for _, v in ary:
        for vi, di in g[v]:
            if d[v]-di == d[vi]:
                memo[vi] = (memo[vi]+memo[v])%MOD
                if d[vi]*2 < d[t-1] < (d[vi] + di)*2:
                    cand.append((vi, v))

    memo2 = [0]*n
    memo2[s-1] = 1

    ary.sort()
    for _, v in ary:
        for vi, di in g[v]:
            if d[v]+di == d[vi]:
                memo2[vi] = (memo2[vi]+memo2[v])%MOD

    cnt = []
    for v1, v2 in cand:
        cnt.append((memo2[v1]*memo[v2])%MOD)

    s = sum(cnt)
    ans = 0
    for ci in cnt:
        ans = (ans+ci*(s-ci))%MOD

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
N, M = map(int, input().split())
S, T = map(int, input().split())
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((v-1, d))
    G[v-1].append((u-1, d))

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

dist = [INF]*N
dist[S] = 0
que = [(0, S)]
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < dist[w]:
            dist[w] = cost + c
            heappush(que, (cost + c, w))

que = deque()
mi = [0]*N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]

D = dist[T]

V = []
E = []
while que:
    v = que.popleft()
    d = dist[v]
    if d*2 == D:
        V.append(v)
    for w, c in G[v]:
        if d == dist[w] + c:
            if dist[w]*2 < D < d*2:
                E.append((w, v))
            H[v].append(w)
            RH[w].append(v)
            if mi[w] == 0:
                mi[w] = 1
                que.append(w)

def bfs(G, RG, s):
    *deg, = map(len, RG)
    que = deque([s])
    res = [0]*N
    res[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            deg[w] -= 1
            res[w] += res[v]
            if deg[w] == 0:
                que.append(w)
                res[w] %= MOD
    return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)

ans = CS[T] * CT[S] % MOD
for v in V:
    ans -= (CS[v] * CT[v]) ** 2
    ans %= MOD
for v, w in E:
    ans -= (CS[v] * CT[w]) ** 2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys

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


def solve(s, t, links):
    q = [(0, 0, s, -1, 0), (0, 0, t, -1, 1)]
    visited_fwd, visited_bwd = [INF] * n, [INF] * n
    patterns_fwd, patterns_bwd = [0] * (n + 1), [0] * (n + 1)
    patterns_fwd[-1] = patterns_bwd[-1] = 1
    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
            patterns_self = patterns_bwd
        else:
            visited_self = visited_fwd
            visited_opp = visited_bwd
            patterns_self = patterns_fwd

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

        patterns_self[v] += patterns_self[a]

        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:
            if cost == collision_time:
                patterns_bwd[v] += patterns_bwd[a]
            continue
        if cost_a == collision_time:
            collision_nodes.add(a)
        elif cost == collision_time:
            collision_nodes.add(v)
            patterns_fwd[v] += patterns_fwd[a]
        else:
            collision_links.add((a, v))

    shortest_count = 0
    collision_count = 0

    for v in collision_nodes:
        if visited_fwd[v] == visited_bwd[v]:
            r = patterns_fwd[v] * patterns_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 = patterns_fwd[u] * patterns_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())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Submission status: Accepted

Solution code:
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())
    # for _ in range(m):
    #     u, v, d = map(int, input().split())
    u -= 1
    v -= 1
    links[u][v] = d
    links[v][u] = d
print(solve(s, t, links))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

# 頂点Sから各頂点への最短路の個数
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

# 頂点Tから各頂点への最短路の個数
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)

Submission status: Runtime Error

Solution code:
from heapq import *
mod=10**9+7
N,M=map(int,input().split())
S,T=map(int,input().split())
S,T=S-1,T-1
G=[[] for i in range(N)]
D1=[0]*N
D2=[0]*N
u,v,d=0,0,0
for i in range(M):
  u,v,d=map(int,input().split())
  u,v=u-1,v-1
  G[u].append((v,d))
  G[v].append((u,d))
INF=10**17
def ijk(s,D):
  global INF,G
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e[0]]>D[v]+e[1]:
        D[e[0]]=D[v]+e[1]
        heappush(Q,(D[e[0]],e[0]))

ijk(S,D1)
ijk(T,D2)
DP1=[-1]*N
DP2=[-1]*N
DP1[S]=1
DP2[T]=1
def f1(n):
  if DP1[n]!=-1:
    return DP1[n]
  DP1[n]=0
  for i in range(len(G[n])):
    if D1[n]==G[n][i][1]+D1[G[n][i][0]]:
      DP1[n]+=f1(G[n][i][0])
  DP1[n]%=mod
  return DP1[n]

def f2(n):
  if DP2[n]!=-1:
    return DP2[n]
  DP2[n]=0
  for i in range(len(G[n])):
    if D2[n]==G[n][i][1]+D2[G[n][i][0]]:
      DP2[n]+=f2(G[n][i][0])
  DP2[n]%=mod
  return DP2[n]

for i in range(N):
  f1(i)
  f2(i)
P=0
X=D1[T]/2
for i in range(N):
  if D1[i]==D2[i]:
    P+=DP1[i]*DP2[i]
  for j in range(len(G[i])):
    if (D1[i]<X and D1[G[i][j][0]]>X)and(D2[i]>X and D2[G[i][j][0]]<X):
      P+=DP1[i]*DP2[G[i][j][0]]
print((DP1[T]*DP2[S]-P)%mod)

Submission status: Runtime Error

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]

    dp1 = [0]*N
    dp2 = [0]*N
    dp1[S] = 1; dp2[T] = 1
    S_collision_points = set()
    S_collision_edges = set()
    que = deque((S))
    while(que):
        now = que.pop()
        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
                que.append(v)
                if distS[v]==L/2:
                    S_collision_points.add(v)
                elif distS[now]<L/2 and L/2<distS[v]:
                    S_collision_edges.add((now,v))
    T_collision_points = set()
    T_collision_edges = set()
    que = [(0,T)]
    """
    while(que):
        d, now = heapq.heappop(que)
        if distT[now] < d: continue
        for v,c in V[now]:
            if distS[v]+distT[now]==L-c:
                dp2[v] += dp2[now]
                dp2[v] %= mod
                heappush(que,(distT[v],v))
                if distT[v]==L/2:
                    T_collision_points.add(v)
                elif distT[now]<L/2 and L/2<distT[v]:
                    T_collision_edges.add((v,now))
    collision_points = S_collision_points & T_collision_points
    collision_edges = S_collision_edges & T_collision_edges
    #print(distS)
    #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]*dp2[p]
            ans += mod
            ans %= mod
            #print(ans,p)
    for u,v in collision_edges:
        ans -= dp1[u]*dp2[v]
        ans += mod
        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
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: Runtime Error

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)
if sum(ansls)%mod != dists[t][1]:
  print(2/0)
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Runtime Error

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)
if sum(ansls) != dists[t][1]:
  print(2/0)
ans = dists[t][1]**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Runtime Error

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

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

mod=10**9+7

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

Sways=[-1]*N
Sways[S-1]=1
def Sdfs(v):
    if Sways[v]!=-1:
        return Sways[v]

    ans=0
    for pv,cost in edge[v]:
        if spath[pv]+cost==spath[v]:
            ans+=Sdfs(pv)
            ans%=mod
    Sways[v]=ans
    return Sways[v]

Sways=[Sdfs(i)%mod for i in range(N)]

Tways=[-1]*N
Tways[T-1]=1
def Tdfs(v):
    if Tways[v]!=-1:
        return Tways[v]

    ans=0
    for pv,cost in edge[v]:
        if tpath[pv]+cost==tpath[v]:
            ans+=Tdfs(pv)
            ans%=mod
    Tways[v]=ans
    return Tways[v]

Tways=[Tdfs(i)%mod for i in range(N)]

ans=Sways[T-1]*Tways[S-1]
ans%=mod
for u,v,d in Edge:
    if 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-=(Tways[v]*Sways[u])**2
        ans%=mod

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

print(ans%mod)