Problem:


Score : 700 points

Problem Statement

We have a graph with N vertices and M edges, and there are two people on the graph: Takahashi and Aoki.

The i-th edge connects Vertex U_i and Vertex V_i.
The time it takes to traverse this edge is D_i minutes, regardless of direction and who traverses the edge (Takahashi or Aoki).

Takahashi departs Vertex S and Aoki departs Vertex T at the same time. Takahashi travels to Vertex T and Aoki travels to Vertex S, both in the shortest time possible.
Find the number of the pairs of ways for Takahashi and Aoki to choose their shortest paths such that they never meet (at a vertex or on an edge) during the travel, modulo 10^9 + 7.

Constraints

1 \leq N \leq 100 000

1 \leq M \leq 200 000

1 \leq S, T \leq N

S \neq T

1 \leq U_i, V_i \leq N (1 \leq i \leq M)

1 \leq D_i \leq 10^9 (1 \leq i \leq M)

If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).

U_i \neq V_i (1 \leq i \leq M)

D_i are integers.

The given graph is connected.

Input

Input is given from Standard Input in the following format:

N M
S T
U_1 V_1 D_1
U_2 V_2 D_2
:
U_M V_M D_M

Output

Print the answer.

Sample Input 1

4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1

Sample Output 1

2

There are two ways to choose shortest paths that satisfies the condition:

Takahashi chooses the path 1 \rightarrow 2 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 4 \rightarrow 1.

Takahashi chooses the path 1 \rightarrow 4 \rightarrow 3, and Aoki chooses the path 3 \rightarrow 2 \rightarrow 1.

Sample Input 2

3 3
1 3
1 2 1
2 3 1
3 1 2

Sample Output 2

2

Sample Input 3

3 3
1 3
1 2 1
2 3 1
3 1 2

Sample Output 3

2

Sample Input 4

8 13
4 2
7 3 9
6 2 3
1 6 4
7 6 9
3 8 9
1 2 2
2 8 12
8 6 9
2 5 5
4 2 18
5 3 7
5 1 515371567
4 8 6

Sample Output 4

6



Sample input:
4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# ARC090E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n, m = map(int, input().split())
s, t = map(int, input().split())
s -= 1
t -= 1
from collections import defaultdict
ns = defaultdict(set)
ds = [None] * m
es = {}
for i in range(m):
    u, v, d = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    ds[i] = d
    es[u-1,v-1] = i
    es[v-1,u-1] = i

def dijkstra(start):
    import heapq
    h = []
    heapq.heapify(h)
    vals = [None] * n
    nums = [None] * n
    nums[start] = 1
    prevs = defaultdict(dict)
    heapq.heappush(h, (0, start)) # (距離, ノード番号, 種類数)
    while h:
        val, u = heapq.heappop(h)
#         print(val, u)
        vals[u] = val
        for v in ns[u]:
            d = ds[es[u,v]]
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                nums[v] = nums[u]
                for vv in ns[v]:
                    prevs[v] = {}
                prevs[v][u] = nums[u]
                heapq.heappush(h, (val+d, v))
            elif vals[v] is not None and vals[v]==val+d:
                prevs[v][u] = nums[u] if u not in prevs[v] else prevs[v][u] + nums[u]
                nums[v] += nums[u]
#                 heapq.heappush(h, (val+d, v))
    return vals, nums, prevs
vals1, nums1, prevs1 = dijkstra(s)
vals2, nums2, prevs2 = dijkstra(t)
T = vals1[t]

ss = set()
q = [t]
while q:
    u = q.pop()
    ss.add(u)
    for v in prevs1[u].keys():
        if v not in ss:
            q.append(v)

c1 = 0 # 頂点で衝突するペアの数
for u in range(n):
    if vals1[u]==T/2 and u in ss:
        c1 += (nums1[u] * nums2[u])**2
c2 = 0 # エッジ(端点除く)で衝突するペアの数
for u in range(n):
    if vals1[u]>=T/2 or u not in ss:
        continue
    for v in ns[u]:
        if vals1[u]>vals1[v] or v not in ss:
            continue
        if vals1[u] + ds[es[u,v]] > T/2:
            c2 += (nums1[u] * nums2[v])**2
#             print(u,v, (nums1[u] * nums2[v])**2)
print(nums1[t]**2 - (c1+c2))

Submission status: Time Limit Exceeded

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]
 
answ = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        answ = (answ - 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]:
                answ = (answ - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(answ)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def dijkstra(start: int, graph: list) -> list:
    """dijkstra法: 始点startから各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|E|log|V|)
    """
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    n = len(graph)
    distance = [INF] * n
    pattern = [0] * n
    distance[start] = 0
    pattern[start] = 1
    q = [(0, start)]  #q = [(startからの距離, 現在地)]
    while q:
        dist, pos = heapq.heappop(q)
        if distance[pos] < dist:
            continue
        for next_pos, cost in graph[pos]:
            if distance[pos] + cost == distance[next_pos]:
                pattern[next_pos] += pattern[pos] % MOD
                heapq.heappush(q, (distance[next_pos], next_pos))
            elif distance[pos] + cost < distance[next_pos]:
                distance[next_pos] = distance[pos] + cost
                pattern[next_pos] = pattern[pos]
                heapq.heappush(q, (distance[next_pos], next_pos))
    return distance, pattern


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 i in range(m):
    a, b, cost = info[i]
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
    
dist_s, ptn_s = dijkstra(s, graph)
dist_t, ptn_t = dijkstra(t, graph)
min_cost, max_ptn = dist_s[t], ptn_s[t]

ans = max_ptn * max_ptn
ans %= MOD

# 頂点上で出会うとき
for i in range(n):
    if dist_s[i] * 2 == min_cost:
        ans -= ptn_s[i] * ptn_t[i]
        ans %= MOD
        
# 辺上で出会うとき
for i in range(n):
    for j, cost in graph[i]:
        if dist_s[i] + cost != dist_s[j]:
            continue
        if dist_t[j] + cost != dist_t[i]:
            continue
        if abs(dist_s[i] - dist_t[j]) < cost:
            ans -= ptn_s[i] * ptn_t[j]
            ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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]*num_t[v])**2
        ans%=mod
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=(num_t[v]*num_s[v])**2
        ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

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 = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn, vn = divmod(k, geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df, vf = divmod(k, geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)*geta)+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*geta+v)
    Edge[v].append(d*geta+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 k in Edge[i]:
        cost, vf = divmod(k, geta)
        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: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 48
    inf = 1<<geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn = k>>geta
        vn = k^(dn<<geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df = k>>geta
            vf = k^(df<<geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)<<geta)+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 = 48
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append(d<<geta|v)
    Edge[v].append(d<<geta|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 k in Edge[i]:
        cost = k>>geta
        vf = k^(cost<<geta)
        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: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 64
    inf = 1<<geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn = k>>geta
        vn = k^(dn<<geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df = k>>geta
            vf = k^(df<<geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)<<geta)+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 = 64
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append(d<<geta|v)
    Edge[v].append(d<<geta|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 k in Edge[i]:
        cost = k>>geta
        vf = k^(cost<<geta)
        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: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 32
    inf = 1<<geta
    dist = [inf] * N
    Q = [s]
    decided = set()
    for _ in range(N):
        while True:
            k = hpp(Q)
            dn = k>>geta
            vn = k^(dn<<geta)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for k in Edge[vn]:
            vf = k>>geta
            df = k^(vf<<geta)
            if vf not in decided:
                hp(Q, ((dn + df)<<geta)+vf)
    return dist

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

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

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

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

onpath = [i for i in range(N) if dists[i] + distt[i] == st]
oset = set(onpath)
Ls = sorted(onpath, key = lambda x: dists[x])
Lt = sorted(onpath, key = lambda x: distt[x])

dps = [0]*N
dpt = [0]*N
dps[S] = 1
dpt[T] = 1
for v in Ls[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if dists[v] + cost + distt[vf] == st:
            dps[vf] = (dps[vf] + dps[v])%MOD
for v in Lt[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if distt[v] + cost + dists[vf] == st:
            dpt[vf] = (dpt[vf] + dpt[v])%MOD

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

Submission status: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 32
    inf = 1<<geta
    dist = [inf] * N
    Q = [s]
    decided = set()
    for _ in range(N):
        while True:
            k = hpp(Q)
            dn = k>>geta
            vn = k^(dn<<geta)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for k in Edge[vn]:
            vf = k>>geta
            df = k^(vf<<geta)
            if vf not in decided:
                hp(Q, ((dn + df)<<geta)+vf)
    return dist

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

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

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

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

onpath = [i for i in range(N) if dists[i] + distt[i] == st]
oset = set(onpath)
Ls = sorted(onpath, key = lambda x: dists[x])
Lt = sorted(onpath, key = lambda x: distt[x])

dps = [0]*N
dpt = [0]*N
dps[S] = 1
dpt[T] = 1
for v in Ls[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if dists[v] + cost + distt[vf] == st:
            dps[vf] = (dps[vf] + dps[v])%MOD
for v in Lt[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if distt[v] + cost + dists[vf] == st:
            dpt[vf] = (dpt[vf] + dpt[v])%MOD

ans = dps[T]**2%MOD
for i in onpath:
    if dists[i] == distt[i]:
        ans = (ans - dps[i]**2%MOD*dpt[i]**2)%MOD
    
    for k in Edge[i]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if dists[i] + cost + distt[vf] == st:
            if dists[i] < st//2 and distt[vf] < st//2:
                ans = (ans - dps[i]**2%MOD*dpt[vf]**2)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 32
    inf = 1<<geta
    dist = [inf] * N
    Q = [s]
    decided = set()
    for _ in range(N):
        while True:
            k = hpp(Q)
            dn = k>>geta
            vn = k^(dn<<geta)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for k in Edge[vn]:
            vf = k>>geta
            df = k^(vf<<geta)
            if vf not in decided:
                hp(Q, ((dn + df)<<geta)+vf)
    return dist

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

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

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

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

onpath = [i for i in range(N) if dists[i] + distt[i] == st]
oset = set(onpath)
Ls = sorted(onpath, key = lambda x: dists[x])
Lt = sorted(onpath, key = lambda x: distt[x])

dps = [0]*N
dpt = [0]*N
dps[S] = 1
dpt[T] = 1
for v in Ls[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if dists[v] + cost + distt[vf] == st:
            dps[vf] = (dps[vf] + dps[v])%MOD
for v in Lt[:-1]:
    for k in Edge[v]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if distt[v] + cost + dists[vf] == st:
            dpt[vf] = (dpt[vf] + dpt[v])%MOD

ans = dps[T]**2%MOD
for i in onpath:
    if dists[i] == distt[i]:
        ans = (ans - dps[i]**2*dpt[i]**2)%MOD
    
    for k in Edge[i]:
        vf = k>>geta
        cost = k^(vf<<geta)
        if dists[i] + cost + distt[vf] == st:
            if dists[i] < st//2 and distt[vf] < st//2:
                ans = (ans - dps[i]**2*dpt[vf]**2)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 32
    inf = 1<<geta
    dist = [inf] * N
    Q = [s]
    decided = set()
    for _ in range(N):
        while True:
            k = hpp(Q)
            dn = k>>geta
            vn = k^(dn<<geta)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for vf, df in Edge[vn]:
            if vf not in decided:
                hp(Q, ((dn + df)<<geta)+vf)
    return dist

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

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

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


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

onpath = [i for i in range(N) if dists[i] + distt[i] == st]
oset = set(onpath)
Ls = sorted(onpath, key = lambda x: dists[x])
Lt = sorted(onpath, key = lambda x: distt[x])

dps = [0]*N
dpt = [0]*N
dps[S] = 1
dpt[T] = 1
for v in Ls[:-1]:
    for vf, cost in Edge[v]:
        if dists[v] + cost + distt[vf] == st:
            dps[vf] = (dps[vf] + dps[v])%MOD
for v in Lt[:-1]:
    for vf, cost in Edge[v]:
        if distt[v] + cost + dists[vf] == st:
            dpt[vf] = (dpt[vf] + dpt[v])%MOD

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    ee = []
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        to[u].append([v, d])
        to[v].append([u, d])
        ee.append([u, v, d])

    # 各頂点までの最短距離distsを作る
    hp = []
    heappush(hp, [0, s])
    dists = [-1] * n
    dist_greater_u = []
    while hp:
        dist, u = heappop(hp)
        if dists[u] != -1: continue
        dists[u] = dist
        dist_greater_u.append(u)
        for v, d in to[u]:
            if dists[v] != -1: continue
            heappush(hp, [dist + d, v])
    # print(dists)

    # sからのs_dag、tからのt_dagを作る
    dag_s = defaultdict(list)
    dag_t = defaultdict(list)
    for u, v, d in ee:
        if dists[u] + d == dists[v]:
            dag_s[u].append(v)
            dag_t[v].append(u)
        if dists[v] + d == dists[u]:
            dag_s[v].append(u)
            dag_t[u].append(v)
    # print(dag_s)
    # print(dag_t)

    # sから各頂点までのルート数way_sとtからのway_tを作る
    way_s = [0] * n
    way_t = [0] * n
    way_s[s] = 1
    for u in dist_greater_u:
        way = way_s[u]
        for v in dag_s[u]:
            way_s[v] += way
    way_t[t] = 1
    for u in dist_greater_u[::-1]:
        way = way_t[u]
        for v in dag_t[u]:
            way_t[v] += way
    # print(way_s)
    # print(way_t)

    # 衝突するルートを数える
    half = dists[t] / 2
    cnt_col = 0
    for u in range(n):
        du = dists[u]
        if du == half:
            cnt_col += pow(way_s[u] * way_t[u], 2, md)
        elif du < half:
            for v in dag_s[u]:
                if dists[v] > half:
                    cnt_col += pow(way_s[u] * way_t[v], 2, md)

    # 全ルートから衝突するルートを引いて答え
    print((way_s[t] ** 2 - cnt_col) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    to = defaultdict(list)
    n, m = map(int, input().split())
    s, t = map(int1, input().split())
    uv_to_ei = {}
    for ei in range(m):
        u, v, d = map(int, input().split())
        u, v = u - 1, v - 1
        uv_to_ei[(u, v)] = uv_to_ei[(v, u)] = ei
        to[u].append([v, d])
        to[v].append([u, d])
    hp = []
    heappush(hp, [0, s])
    while hp:
        dist, u = heappop(hp)
        if u == t:
            min_dist = dist
            break
        for v, d in to[u]:
            heappush(hp, [dist + d, v])
    # print(min_dist)
    half = min_dist / 2
    dists = [-1] * n
    hp = []
    heappush(hp, [0, s, -1, 1])
    ways = defaultdict(int)
    while hp:
        dist, u, h0, way = heappop(hp)
        if u == t and dist == min_dist:
            ways[h0] += way
            continue
        if dists[u] == -1: dists[u] = dist
        if dists[u] != dist: continue
        for v, d in to[u]:
            nd = dist + d
            if nd == half:
                h0 = v
            elif dist < half < nd:
                h0 = uv_to_ei[(u, v)] + n
            heappush(hp, [dist + d, v, h0, way])
    # print(uv_to_ei)
    # print(ways)
    sum_v = 0
    sum_v2 = 0
    for k, v in ways.items():
        sum_v += v
        sum_v2 += v ** 2
    print(sum_v ** 2 - sum_v2)

main()

Submission status: Time Limit Exceeded

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)

    n_paths_S = [-1] * (N+1)
    n_paths_T = [-1] * (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)

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

Solution code:
def main():
    import sys
    sys.setrecursionlimit(500000)
    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 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

        import numpy as np
        from scipy.sparse import csr_matrix, csgraph
        V, U, D = np.array(edges).T
        graph = csr_matrix((D, (V, U)), (N+1, N+1))
        return list(csgraph.dijkstra(graph, indices=start, directed=False))

    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)

    n_paths_S = [-1] * (N+1)
    n_paths_T = [-1] * (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 += calc_n_paths_S(u)
        res %= 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 += calc_n_paths_T(u)
        res %= mod
        n_paths_T[v] = res
        return res

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

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