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 sys
import heapq as hq

mod = 10**9 + 7

readline = sys.stdin.buffer.readline

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

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


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

solve()

Submission status: Accepted

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:
    dx,x = hq.heappop(q)
    k = dist[x][1]
    for y,d in graph[x]:
      if dist[y][0] > dx+d:
        dist[y][0] = dx+d
        dist[y][1] = k
        hq.heappush(q,(dist[y][0],y))
      elif dist[y][0] == dx+d:
        dist[y][1] = (dist[y][1]+k)%mod
dst = dists[t][0]
ansls = []
for u,v,d in abd:
  for a,b in (u,v),(v,u):
    if dists[a][0] < distt[a][0]:
      if dists[a][0]*2 < dst and distt[b][0]*2 < dst:
        if dists[a][0]+distt[b][0]+d == dst:
          ansls.append(dists[a][1]*distt[b][1]%mod)
for v in range(1,n+1):
  if dists[v][0]*2 == distt[v][0]*2 == dst:
    ansls.append(dists[v][1]*distt[v][1]%mod)
sm = sum(ansls)%mod
ans = sm**2%mod
for i in ansls:
  ans = (ans-i**2)%mod
print(ans)

Submission status: Accepted

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

print(ans%mod)

Submission status: Accepted

Solution code:
mod=10**9+7

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

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

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

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

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

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

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

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

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        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)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

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

import sys

input=sys.stdin.readline
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)

Submission status: Accepted

Solution code:
# ARC090E

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

Submission status: Accepted

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

INF = 10**18
mod = 10**9+7
# AOJ GRL_1_A Single Sourse Shortest Path
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)] # 頂点iへの最短距離がD[i]
    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)

Submission status: Accepted

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

Submission status: Accepted

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    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

    #reverse
    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

    #print(route)
    #print(route2)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(100000)
    input = sys.stdin.readline
    from heapq import heappop, heappush
    mod = 10**9+7
    INF = 1<<60
    N, M = map(int, input().split())
    S, T = map(int, input().split())
    E = [[] for _ in range(N+1)]
    edges = []
    # for _ in range(M):
    #     u, v, d = map(int, input().split())
    #     E[u].append((v, d))
    #     E[v].append((u, d))
    #     edges.append((u, v, d))
    for u, v, d in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        E[u].append((v, d))
        E[v].append((u, d))
        edges.append((u, v, d))

    def dijksrtra(start):
        Dist = [INF] * (N+1)
        Dist[start] = 0
        q = [0<<17 | start]
        mask = (1<<17)-1
        while q:
            dist_v = heappop(q)
            v = dist_v & mask
            dist = dist_v >> 17
            if Dist[v] != dist:
                continue
            for u, d in E[v]:
                new_dist = dist + d
                if Dist[u] > new_dist:
                    Dist[u] = new_dist
                    heappush(q, new_dist<<17 | u)
        return Dist

    Dist_S = dijksrtra(S)
    Dist_T = dijksrtra(T)
    dist_st = Dist_S[T]

    DAG_edges = []  # S -> T
    DAG = [[] for _ in range(N+1)]
    DAG_rev = [[] for _ in range(N+1)]
    for u, v, d in edges:
        if Dist_S[u] + Dist_T[v] + d == dist_st:
            DAG_edges.append((u, v))
            DAG[u].append(v)
            DAG_rev[v].append(u)
        elif Dist_T[u] + Dist_S[v] + d == dist_st:
            DAG_edges.append((v, u))
            DAG[v].append(u)
            DAG_rev[u].append(v)


    # トポロジカルソート
    V = []
    rem = [0] * (N+1)
    for _, v in DAG_edges:
        rem[v] += 1
    q = [S]
    while q:
        v = q.pop()
        V.append(v)
        for u in DAG[v]:
            rem[u] -= 1
            if rem[u] == 0:
                q.append(u)


    # n_paths_S = [-1] * (N+1)
    # n_paths_T = [-1] * (N+1)
    n_paths_S = [0] * (N+1)
    n_paths_T = [0] * (N+1)
    n_paths_S[S] = 1
    n_paths_T[T] = 1
    # def calc_n_paths_S(v):
    #     if n_paths_S[v] != -1:
    #         return n_paths_S[v]
    #     res = 0
    #     for u in DAG_rev[v]:
    #         res = (res + calc_n_paths_S(u)) % mod
    #     n_paths_S[v] = res
    #     return res
    # def calc_n_paths_T(v):
    #     if n_paths_T[v] != -1:
    #         return n_paths_T[v]
    #     res = 0
    #     for u in DAG[v]:
    #         res = (res + calc_n_paths_T(u)) % mod
    #     n_paths_T[v] = res
    #     return res

    # ans = calc_n_paths_S(T)  # 全経路数
    # calc_n_paths_T(S)

    for v in V:
        n = n_paths_S[v]
        for u in DAG[v]:
            n_paths_S[u] += n
    for v in V[::-1]:
        n = n_paths_T[v]
        for u in DAG_rev[v]:
            n_paths_T[u] += n
    ans = n_paths_S[T]
    ans = ans * ans % mod

    for v, u in DAG_edges:  # 辺ですれ違う場合
        if Dist_S[v]*2 < dist_st and dist_st < Dist_S[u]*2:
            ans = (ans - (n_paths_S[v]*n_paths_T[u])**2) % mod

    # 頂点ですれ違う場合
    for v, (dist, ns, nt) in enumerate(zip(Dist_S, n_paths_S, n_paths_T)):
        if dist*2 == dist_st:
            ans = (ans - (ns*nt)**2) % mod

    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = 1000000007


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


def dijkstra(graph, start=0):
    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 v, c 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


route_cnt, dist = dijkstra(G, s - 1)
r_route_cnt, r_dist = dijkstra(G, t - 1)
total_dist = dist[t - 1]
ret = 0
for i in range(n):
    if dist[i] == r_dist[i]:
        ret = ret + (route_cnt[i] * r_route_cnt[i] % mod) ** 2 % mod


for u in range(n):
    for v, c in G[u]:
        if dist[u] < total_dist / 2 < dist[v] and dist[u] + c + r_dist[v] == total_dist:
            ret = (ret + route_cnt[u] ** 2 % mod * r_route_cnt[v] ** 2 % mod) % mod


print((route_cnt[t - 1] ** 2 - ret) % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import *

"""
とりあえず何通りあるかを数える：各頂点を通る時点での場合の数
最後に衝突する方法を除外する：頂点での衝突、辺での衝突
辺での衝突：距離を見れば分かる
"""

MOD = 10 ** 9 + 7

N,M = map(int,input().split())
S,T = map(int,input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v,d = map(int,input().split())
    graph[u].append((v,d))
    graph[v].append((u,d))

def dijkstra(S):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[S] = 1
    q = [(0,S)] # 距離、場所
    while q:
        d,x = heappop(q)
        if dist[x] < d:
            continue
        dist[x] = d
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            if d + dy == dist[y]:
                cnt_path[y] += cnt_path[x]
                continue
            cnt_path[y] = cnt_path[x]
            dist[y] = d + dy
            heappush(q,(d+dy,y))
    return dist, cnt_path

dist_S, cnt_path_S = dijkstra(S)
dist_T, cnt_path_T = dijkstra(T)

D = dist_S[T]
# 最短路の組
answer = cnt_path_S[T] * cnt_path_T[S]
# 頂点での衝突
for x in range(1,N+1):
    if dist_S[x] == dist_T[x]:
        t = cnt_path_S[x] * cnt_path_T[x] % MOD
        answer -= t * t % MOD
# 辺での衝突。S側がx、T側がy
for x in range(1,N+1):
    for y,d in graph[x]:
        dx = dist_S[x]
        dy = dist_T[y]
        if dx + dy + d == D and dx + d > dy and dy + d > dx:
            t = cnt_path_S[x] * cnt_path_T[y] % MOD
            answer -= t * t % MOD

answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))

N, M = inpl()
S, T = inpl()
G = [[] for _ in range(N+1)]
MOD = 10**9 + 7
for _ in range(M):
    u, v, d = inpl()
    G[u].append((v, d))
    G[v].append((u, d))

cost = [10**18]*(N+1)
appear = [0]*(N+1)

Q = [(0, S)]
cost[S] = 0
appear[S] = 1

while Q:
    c, p = heappop(Q)
    if cost[p] < c:
        continue
    for q, d in G[p]:
        if cost[p] + d == cost[q]:
            appear[q] = (appear[q] + appear[p])%MOD
        elif cost[p] + d < cost[q]:
            cost[q] = cost[p] + d
            appear[q] = appear[p] % MOD
            heappush(Q, (cost[q], q))

end = cost[T]*1
ans = pow(appear[T], 2, MOD)

Q = [(0, T)]
cost2 = [10**18]*(N+1)
cost2[T] = 0
appear2 = [0]*(N+1)
appear2[T] = 1
while Q:
    c, p = heappop(Q)
    if cost2[p] < c:
        continue
    for q, d in G[p]:
        if cost[p] - d != cost[q]:
            continue
        if cost2[p] + d == cost2[q]:
            appear2[q] = (appear2[q] + appear2[p])%MOD
        elif cost2[p] + d < cost2[q]:
            cost2[q] = cost2[p] + d
            appear2[q] = appear2[p] % MOD
            heappush(Q, (cost2[q], q))

Q = deque([S])
searched = [False]*(N+1)
searched[S] = True

while Q:
    p = Q.pop()
    if 2*cost2[p] == end:
        ans = (ans - (appear[p]*appear2[p])**2)%MOD

    for q, d in G[p]:
        if cost2[p] - d != cost2[q]:
            continue
        if 2*cost2[q] < end < 2*cost2[p]:
            ans = (ans - (appear[p]*appear2[q])**2)%MOD
        if not searched[q]:
            Q.append(q)
            searched[q] = True
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

INF = float('inf')
MOD = 10**9 + 7

def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    nums = [0] * numV
    nums[vSt] = 1
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                nums[v2] = nums[vNow]
                heappush(PQ, (c2, v2))
            elif c2 == costs[v2]:
                nums[v2] = (nums[v2]+nums[vNow]) % MOD
    return (costs, nums)

def solve():
    N, M = map(int, input().split())
    S, T = map(int, input().split())
    S, T = S-1, T-1
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    adjL = [[] for _ in range(N)]
    for u, v, d in edges:
        adjL[u-1].append((v-1, d))
        adjL[v-1].append((u-1, d))

    costSs, numSs = Dijkstra(adjL, S)
    costTs, numTs = Dijkstra(adjL, T)
    minCost = costSs[T]

    ans = (numSs[T]**2) % MOD
    for v in range(N):
        if costSs[v] == costTs[v] == minCost/2:
            k = (numSs[v]*numTs[v]) % MOD
            ans -= (k**2) % MOD
            ans %= MOD
    for u, v, d in edges:
        u, v = u-1, v-1
        if costSs[u] > costSs[v]:
            u, v = v, u
        if costSs[u] < minCost/2 and costTs[v] < minCost/2 and costSs[u]+d+costTs[v] == minCost:
            k = (numSs[u]*numTs[v]) % MOD
            ans -= (k**2) % MOD
            ans %= MOD

    print(ans)

solve()

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
S,T=map(int,input().split())
Graph=[set() for i in range(N)]
Edge=[]
mod=10**9+7
inf=float("inf")
for i in range(M):
  a,b,c=map(int,input().split())
  Graph[a-1].add((c,b-1))
  Graph[b-1].add((c,a-1))
  Edge.append((a-1,b-1,c))
  Edge.append((b-1,a-1,c))
def dijkstra(s,n,links):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

def dp(s,n,links,d):
  Visited=[False]*n
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    if 2*hc>d:
      break
    if Visited[hp]:
      continue
    Visited[hp]=True
    for c,p in links[hp]:
      if Visited[p]:
        continue
      if c+hc<cost[p]:
        cost[p]=c+hc
        P[p]=P[hp]
        heappush(heap,(cost[p],p))
      elif c+hc==cost[p]:
        P[p]=(P[p]+P[hp])%mod
  return cost,P

cost_S,P_S=dijkstra(S-1,N,Graph)
D=cost_S[T-1]
cost_T,P_T=dp(T-1,N,Graph,D)
Pat=P_S[T-1]
ans=(Pat**2)%mod
for a,b,c in Edge:
  if cost_S[a]+cost_T[b]+c==D:
    if 2*cost_S[a]<D and 2*cost_T[b]<D:
      ans-=((P_S[a]*P_T[b])**2)%mod
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=((P_S[i]*P_T[i])**2)%mod
print(ans%mod)