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:
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 ** 20
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()
graph = [[] for _ in range(n)]
for i in range(m):
    u, v, d = map(int, input().split())
    graph[u - 1] += [(v - 1, d)]
    graph[v - 1] += [(u - 1, d)]

vst = s - 1
v_g = t - 1
checked = [0] * n
dist = [INF] * n
route_cnt = [0] * n
route_cnt[vst] = 1
dist[vst] = 0
for _ in range(n):
    min_dist = INF
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v]:
            continue
        if dist[target_v] + cost < dist[to_v]:
            dist[to_v] = dist[target_v] + cost
            route_cnt[to_v] = route_cnt[target_v]
        elif dist[target_v] + cost == dist[to_v]:
            route_cnt[to_v] = (route_cnt[to_v] + route_cnt[target_v]) % mod
    if target_v == v_g:
        break

total_dist = dist[v_g]
half_dist = dist[v_g] / 2
enc_li = []
checked = [0] * n
reverse_dist = [INF] * n
reverse_route_cnt = [0] * n
reverse_route_cnt[v_g] = 1
reverse_dist[v_g] = 0
for _ in range(n):
    min_dist = INF
    for i in range(n):
        if checked[i] == 0 and reverse_dist[i] < min_dist:
            target_v = i
            min_dist = reverse_dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v] or reverse_dist[target_v] + cost != total_dist - dist[to_v]:
            continue
        if reverse_dist[target_v] + cost < reverse_dist[to_v]:
            reverse_dist[to_v] = reverse_dist[target_v] + cost
            reverse_route_cnt[to_v] = reverse_route_cnt[target_v]
        elif reverse_dist[target_v] + cost == reverse_dist[to_v]:
            reverse_route_cnt[to_v] = (reverse_route_cnt[target_v] + reverse_route_cnt[to_v]) % mod
        if reverse_dist[target_v] <= half_dist < reverse_dist[to_v]:
            enc_li += [(to_v, target_v)]

ret = 0
for from_v, to_v, in enc_li:
    ret += route_cnt[from_v] * reverse_route_cnt[to_v] % mod
    ret %= mod

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

Submission status: Time Limit Exceeded

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 ** 20
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()
graph = [[] for _ in range(n)]
for i in range(m):
    u, v, d = map(int, input().split())
    graph[u - 1] += [(v - 1, d)]
    graph[v - 1] += [(u - 1, d)]

vst = s - 1
v_g = t - 1
checked = [0] * n
dist = [float('inf')] * n
route_cnt = [0] * n
route_cnt[vst] = 1
dist[vst] = 0
for _ in range(n):
    min_dist = INF
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v]:
            continue
        if dist[target_v] + cost < dist[to_v]:
            dist[to_v] = dist[target_v] + cost
            route_cnt[to_v] = route_cnt[target_v]
        elif dist[target_v] + cost == dist[to_v]:
            route_cnt[to_v] = (route_cnt[to_v] + route_cnt[target_v]) % mod
    if target_v == v_g:
        break

total_dist = dist[v_g]
half_dist = dist[v_g] / 2
enc_li = []
checked = [0] * n
reverse_dist = [INF] * n
reverse_route_cnt = [0] * n
reverse_route_cnt[v_g] = 1
reverse_dist[v_g] = 0
for _ in range(n):
    min_dist = INF
    for i in range(n):
        if checked[i] == 0 and reverse_dist[i] < min_dist:
            target_v = i
            min_dist = reverse_dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v] or reverse_dist[target_v] + cost != total_dist - dist[to_v]:
            continue
        if reverse_dist[target_v] + cost < reverse_dist[to_v]:
            reverse_dist[to_v] = reverse_dist[target_v] + cost
            reverse_route_cnt[to_v] = reverse_route_cnt[target_v]
        elif reverse_dist[target_v] + cost == reverse_dist[to_v]:
            reverse_route_cnt[to_v] = (reverse_route_cnt[target_v] + reverse_route_cnt[to_v]) % mod
        if reverse_dist[target_v] <= half_dist < reverse_dist[to_v]:
            enc_li += [(to_v, target_v)]

ret = 0
for from_v, to_v, in enc_li:
    ret += route_cnt[from_v] * reverse_route_cnt[to_v] % mod
    ret %= mod

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7


n, m = map(int, input().split())
s, t = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    u, v, d = map(int, input().split())
    graph[u - 1] += [(v - 1, d)]
    graph[v - 1] += [(u - 1, d)]

vst = s - 1
v_g = t - 1
checked = [0] * n
dist = [float('inf')] * n
route_cnt = [0] * n
route_cnt[vst] = 1
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v]:
            continue
        if dist[target_v] + cost < dist[to_v]:
            dist[to_v] = dist[target_v] + cost
            route_cnt[to_v] = route_cnt[target_v]
        elif dist[target_v] + cost == dist[to_v]:
            route_cnt[to_v] = (route_cnt[to_v] + route_cnt[target_v]) % mod
    if target_v == v_g:
        break

total_dist = dist[v_g]
half_dist = dist[v_g] / 2
enc_li = []
checked = [0] * n
reverse_dist = [float('inf')] * n
reverse_route_cnt = [0] * n
reverse_route_cnt[v_g] = 1
reverse_dist[v_g] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and reverse_dist[i] < min_dist:
            target_v = i
            min_dist = reverse_dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v] or reverse_dist[target_v] + cost != total_dist - dist[to_v]:
            continue
        if reverse_dist[target_v] + cost < reverse_dist[to_v]:
            reverse_dist[to_v] = reverse_dist[target_v] + cost
            reverse_route_cnt[to_v] = reverse_route_cnt[target_v]
        elif reverse_dist[target_v] + cost == reverse_dist[to_v]:
            reverse_route_cnt[to_v] = (reverse_route_cnt[target_v] + reverse_route_cnt[to_v]) % mod
        if reverse_dist[target_v] <= half_dist < reverse_dist[to_v]:
            enc_li += [(to_v, target_v)]

ret = 0
for from_v, to_v, in enc_li:
    ret += route_cnt[from_v] * reverse_route_cnt[to_v] % mod
    ret %= mod

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s, t = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    u, v, d = map(int, input().split())
    graph[u - 1] += [(v - 1, d)]
    graph[v - 1] += [(u - 1, d)]


vst = s - 1
v_g = t - 1
checked = [0] * n
dist = [float('inf')] * n
route_cnt = [0] * n
route_cnt[vst] = 1
dist[vst] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and dist[i] < min_dist:
            target_v = i
            min_dist = dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v]:
            continue
        if dist[target_v] + cost < dist[to_v]:
            dist[to_v] = dist[target_v] + cost
            route_cnt[to_v] = route_cnt[target_v]
        elif dist[target_v] + cost == dist[to_v]:
            route_cnt[to_v] += route_cnt[target_v]
    if target_v == v_g:
        break


total_dist = dist[v_g]
half_dist = dist[v_g] / 2
enc_li = []
checked = [0] * n
reverse_dist = [float('inf')] * n
reverse_route_cnt = [0] * n
reverse_route_cnt[v_g] = 1
reverse_dist[v_g] = 0
for _ in range(n):
    min_dist = float('inf')
    for i in range(n):
        if checked[i] == 0 and reverse_dist[i] < min_dist:
            target_v = i
            min_dist = reverse_dist[i]
    checked[target_v] = 1
    for to_v, cost in graph[target_v]:
        if checked[to_v] or reverse_dist[target_v] + cost != total_dist - dist[to_v]:
            continue
        if reverse_dist[target_v] + cost < reverse_dist[to_v]:
            reverse_dist[to_v] = reverse_dist[target_v] + cost
            reverse_route_cnt[to_v] = reverse_route_cnt[target_v]
        elif reverse_dist[target_v] + cost == reverse_dist[to_v]:
            reverse_route_cnt[to_v] += reverse_route_cnt[target_v]
        if reverse_dist[target_v] <= half_dist < reverse_dist[to_v]:
            enc_li += [(to_v, target_v)]


ret = 0
for from_v, to_v, in enc_li:
    ret += route_cnt[from_v] * reverse_route_cnt[to_v]




print(route_cnt[v_g] ** 2 - ret)

Submission status: Time Limit Exceeded

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,T):
    # 距離、パスの個数を返す
    INF = 10 ** 15
    dist = [INF] * (N+1)
    cnt_path = [0] * (N+1)
    cnt_path[0] = 1
    q = [(0,S,0)] # 距離、場所、直前
    while q:
        d,x,pred = heappop(q)
        if dist[T] < d:
            break
        if dist[x] < d:
            continue
        if dist[x] == d:
            cnt_path[x] += cnt_path[pred]
            cnt_path[x] %= MOD
            continue
        dist[x] = d
        cnt_path[x] = cnt_path[pred]
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            heappush(q,(d+dy,y,x))
    return dist, cnt_path

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

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

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[0] = 1
    q = [(0,S,0)] # 距離、場所、直前
    while q:
        d,x,pred = heappop(q)
        if dist[x] < d:
            continue
        if dist[x] == d:
            cnt_path[x] += cnt_path[pred]
            cnt_path[x] %= MOD
            continue
        dist[x] = d
        cnt_path[x] = cnt_path[pred]
        for y,dy in graph[x]:
            if d + dy > dist[y]:
                continue
            heappush(q,(d+dy,y,x))
    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: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
N, M = map(int, input().split())
S, T = map(int, input().split())
E_ = [list(map(int, input().split())) for _ in range(M)]
E = [[] for _ in range(N+1)]
for U, V, D in E_:
    E[U].append([V, D])
    E[V].append([U, D])

E_S = [[] for _ in range(N+1)]
dist_S = [float("inf") for _ in range(N+1)]
dist_S[S] = 0
cnt_S = [0] * (N+1)
cnt_S[S] = 1
q = [(0, S, 0, 0)]
dist_st = float("inf")
closed = [False] * (N+1)
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_S[v] < prov_cost:
        continue

    cnt_S[v] += cnt_S[from_]
    E_S[v].append([from_, d])

    if closed[v]:
        continue
    if dist_st < prov_cost:
        break
    if v == T:
        dist_st = prov_cost
    closed[v] = True
    for u, d in E[v]:
        cost_new = prov_cost + d
        if dist_S[u] >= cost_new:
            dist_S[u] = cost_new
            heapq.heappush(q, (cost_new, u, v, d))
cnt_st = cnt_S[T]

d2 = (dist_st+1)//2
dist_T = [float("inf") for _ in range(N+1)]
cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [(0, T, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_T[v] < prov_cost:
        continue

    cnt_T[v] += cnt_T[from_]

    if dist_T[v] == prov_cost:
        continue
    dist_T[v] = prov_cost
    if d2 < prov_cost:
        break
    for u, d in E[v]:
        if dist_T[u] > prov_cost + d:
            heapq.heappush(q, (prov_cost+d, u, v, d))

ans = cnt_st * cnt_st

if dist_st % 2 == 0:
    d2 = dist_st//2
    for i, (ds, dt) in enumerate(zip(dist_S, dist_T)):
        if d2==ds==dt:
            c = cnt_S[i] * cnt_T[i]
            ans -= c*c
d2 = (dist_st+1) // 2
for u, v, d in E_:
    dsu = dist_S[u]
    dtv = dist_T[v]
    if dsu < d2 and dtv < d2 and dsu + dtv + d == dist_st:
        c = cnt_S[u] * cnt_T[v]
        ans -= c*c
    dsv = dist_S[v]
    dtu = dist_T[u]
    if dsv < d2 and dtu < d2 and dsv +dtu + d == dist_st:
        c = cnt_S[v] * cnt_T[u]
        ans -= c*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
N, M = map(int, input().split())
S, T = map(int, input().split())
E_ = [list(map(int, input().split())) for _ in range(M)]
E = [[] for _ in range(N+1)]
for U, V, D in E_:
    E[U].append([V, D])
    E[V].append([U, D])

E_S = [[] for _ in range(N+1)]
dist_S = [float("inf") for _ in range(N+1)]
cnt_S = [0] * (N+1)
cnt_S[S] = 1
q = [(0, S, 0, 0)]
dist_st = float("inf")
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_S[v] < prov_cost:
        continue

    cnt_S[v] += cnt_S[from_]
    E_S[v].append([from_, d])

    if dist_S[v] == prov_cost:
        continue
    if dist_st < prov_cost:
        break
    dist_S[v] = prov_cost
    if v == T:
        dist_st = prov_cost
    for u, d in E[v]:
        if dist_S[u] > prov_cost + d:
            heapq.heappush(q, (prov_cost+d, u, v, d))

cnt_st = cnt_S[T]

d2 = (dist_st+1)//2
dist_T = [float("inf") for _ in range(N+1)]
cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [(0, T, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_T[v] < prov_cost:
        continue

    cnt_T[v] += cnt_T[from_]

    if dist_T[v] == prov_cost:
        continue
    dist_T[v] = prov_cost
    if d2 < prov_cost:
        break
    for u, d in E[v]:
        if dist_T[u] > prov_cost + d:
            heapq.heappush(q, (prov_cost+d, u, v, d))

ans = cnt_st * cnt_st

if dist_st % 2 == 0:
    d2 = dist_st//2
    for i, (ds, dt) in enumerate(zip(dist_S, dist_T)):
        if d2==ds==dt:
            c = cnt_S[i] * cnt_T[i]
            ans -= c*c
d2 = (dist_st+1) // 2
for u, v, d in E_:
    dsu = dist_S[u]
    dtv = dist_T[v]
    if dsu < d2 and dtv < d2 and dsu + dtv + d == dist_st:
        c = cnt_S[u] * cnt_T[v]
        ans -= c*c
    dsv = dist_S[v]
    dtu = dist_T[u]
    if dsv < d2 and dtu < d2 and dsv +dtu + d == dist_st:
        c = cnt_S[v] * cnt_T[u]
        ans -= c*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
N, M = map(int, input().split())
S, T = map(int, input().split())
E_ = [list(map(int, input().split())) for _ in range(M)]
E = [[] for _ in range(N+1)]
for U, V, D in E_:
    E[U].append([V, D])
    E[V].append([U, D])

E_S = [[] for _ in range(N+1)]
dist_S = [float("inf") for _ in range(N+1)]
cnt_S = [0] * (N+1)
cnt_S[S] = 1
q = [(0, S, 0, 0)]
dist_st = float("inf")
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_S[v] < prov_cost:
        continue

    cnt_S[v] += cnt_S[from_]
    E_S[v].append([from_, d])

    if dist_S[v] == prov_cost:
        continue
    if dist_st < prov_cost:
        break
    dist_S[v] = prov_cost
    if v == T:
        dist_st = prov_cost
    for u, d in E[v]:
        if dist_S[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

cnt_st = cnt_S[T]

d2 = (dist_st+1)//2
dist_T = [float("inf") for _ in range(N+1)]
cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [(0, T, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_T[v] < prov_cost:
        continue

    cnt_T[v] += cnt_T[from_]

    if dist_T[v] == prov_cost:
        continue
    dist_T[v] = prov_cost
    if d2 < prov_cost:
        break
    for u, d in E[v]:
        if dist_T[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

ans = cnt_st * cnt_st

if dist_st % 2 == 0:
    d2 = dist_st//2
    for i, (ds, dt) in enumerate(zip(dist_S, dist_T)):
        if d2==ds==dt:
            c = cnt_S[i] * cnt_T[i]
            ans -= c*c
d2 = (dist_st+1) // 2
for u, v, d in E_:
    dsu = dist_S[u]
    dtv = dist_T[v]
    if dsu < d2 and dtv < d2 and dsu + dtv + d == dist_st:
        c = cnt_S[u] * cnt_T[v]
        ans -= c*c
    dsv = dist_S[v]
    dtu = dist_T[u]
    if dsv < d2 and dtu < d2 and dsv +dtu + d == dist_st:
        c = cnt_S[v] * cnt_T[u]
        ans -= c*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S, T = map(int, input().split())
E_ = [list(map(int, input().split())) for _ in range(M)]
E = [[] for _ in range(N+1)]
for U, V, D in E_:
    E[U].append([V, D])
    E[V].append([U, D])

E_S = [[] for _ in range(N+1)]
dist_S = [float("inf") for _ in range(N+1)]
cnt_S = [0] * (N+1)
cnt_S[S] = 1
q = [(0, S, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_S[v] < prov_cost:
        continue

    cnt_S[v] += cnt_S[from_]
    E_S[v].append([from_, d])

    if dist_S[v] == prov_cost:
        continue
    dist_S[v] = prov_cost

    for u, d in E[v]:
        if dist_S[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

dist_st = dist_S[T]
cnt_st = cnt_S[T]

dist_T = [float("inf") for _ in range(N+1)]
cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [(0, T, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_T[v] < prov_cost:
        continue

    cnt_T[v] += cnt_T[from_]

    if dist_T[v] == prov_cost:
        continue
    dist_T[v] = prov_cost

    for u, d in E[v]:
        if dist_T[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

ans = cnt_st * cnt_st

if dist_st % 2 == 0:
    d2 = dist_st//2
    for i, (ds, dt) in enumerate(zip(dist_S, dist_T)):
        if d2==ds==dt:
            c = cnt_S[i] * cnt_T[i]
            ans -= c*c
d2 = (dist_st+1) // 2
for u, v, d in E_:
    if dist_S[u] < d2 and dist_T[v] < d2 and dist_S[u] + dist_T[v] + d == dist_st:
        c = cnt_S[u] * cnt_T[v]
        ans -= c*c
    if dist_S[v] < d2 and dist_T[u] < d2 and dist_S[v] + dist_T[u] + d == dist_st:
        c = cnt_S[v] * cnt_T[u]
        ans -= c*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
S, T = map(int, input().split())
E_ = [list(map(int, input().split())) for _ in range(M)]
E = [[] for _ in range(N+1)]
for U, V, D in E_:
    E[U].append([V, D])
    E[V].append([U, D])

E_S = [[] for _ in range(N+1)]
dist_S = [float("inf") for _ in range(N+1)]
cnt_S = [0] * (N+1)
cnt_S[S] = 1
q = [(0, S, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_S[v] < prov_cost:
        continue

    cnt_S[v] += cnt_S[from_]
    E_S[v].append([from_, d])

    if dist_S[v] == prov_cost:
        continue
    dist_S[v] = prov_cost

    for u, d in E[v]:
        if dist_S[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

dist_st = dist_S[T]
cnt_st = cnt_S[T]

dist_T = [float("inf") for _ in range(N+1)]
cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [(0, T, 0, 0)]
while len(q)!=0:
    prov_cost, v, from_, d = heapq.heappop(q)
    if dist_T[v] < prov_cost:
        continue

    cnt_T[v] += cnt_T[from_]

    if dist_T[v] == prov_cost:
        continue
    dist_T[v] = prov_cost

    for u, d in E[v]:
        if dist_T[u] == float("inf"):
            heapq.heappush(q, (prov_cost+d, u, v, d))

ans = cnt_st * cnt_st

if dist_st % 2 == 0:
    d2 = dist_st//2
    for i, (ds, dt) in enumerate(zip(dist_S, dist_T)):
        if d2==ds==dt:
            c = cnt_S[i] * cnt_T[i]
            ans -= c*c
d2 = (dist_st+1) // 2
for u, v, d in E_:
    if dist_S[u] < d2 and dist_T[v] < d2 and dist_S[u] + dist_T[v] + d == dist_st:
        c = cnt_S[u] * cnt_T[v]
        ans -= c*c
    if dist_S[v] < d2 and dist_T[u] < d2 and dist_S[v] + dist_T[u] + d == dist_st:
        c = cnt_S[v] * cnt_T[u]
        ans -= c*c
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

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

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

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

			self.cnt += 1
		#print(self.dp)
		return

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import heapq

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

def solve(n, m, s, t, edges):

    dist = [[INF] * n for _ in range(2)]
    dist[0][s] = 0
    dist[1][t] = 0

    dp = [[0] * n for _ in range(2)]
    dp[0][s] = 1
    dp[1][t] = 1

    target = [t, s]

    for i in range(2):
        target_i = target[i]
        dist_i = dist[i]
        dp_i = dp[i]
        q = []

        for v in range(n):
            heapq.heappush(q, (dist_i[v], v))

        end = False
        while 0 < len(q):
            du, u = heapq.heappop(q)
            if du != dist_i[u]:
                continue
            if end and dist_i[target_i] < du:
                break
            for v, d in edges[u]:
                alt = du + d
                if dist_i[v] > alt:
                    dist_i[v] = alt
                    dp_i[v] = dp_i[u]
                    heapq.heappush(q, (alt, v))
                elif dist_i[v] == alt:
                    dp_i[v] += dp_i[u]
                if v == target_i:
                    end = True

    spt = dist[0][t]

    c_point = set()
    n_point = set()
    f_point = set()
    c_edge = set()
    for v in range(n):
        if dist[0][v] + dist[1][v] == spt:
            if dist[0][v] == dist[1][v]:
                c_point.add(v)
            elif dist[0][v] < dist[1][v]:
                n_point.add(v)
            else:
                f_point.add(v)

    for u in n_point:
        for v, d in edges[u]:
            if v in f_point:
                if dist[0][u] + d + dist[1][v] == spt:
                    c_edge.add((u, v))


    ans = 0
    for u in c_point:
        dpu = dp[0][u] * dp[1][u]
        for v in c_point:
            if u == v: continue
            ans += dpu * dp[0][v] * dp[1][v]
            ans %= MOD
        for vn, vf in c_edge:
            ans += dpu * dp[0][vn] * dp[1][vf]
            ans %= MOD
    for un, uf in c_edge:
        dpu = dp[0][un] * dp[1][uf]
        for v in c_point:
            ans += dpu * dp[0][v] * dp[1][v]
            ans %= MOD
        for vn, vf in c_edge:
            if un == vn and uf == vf: continue
            ans += dpu * dp[0][vn] * dp[1][vf]
            ans %= MOD

    return ans


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s, t = input().split()
    s = int(s) - 1
    t = int(t) - 1
    edges = [[] for _ in range(n)]
    for _ in range(m):
        u, v, d = input().split()
        u = int(u) - 1
        v = int(v) - 1
        d = int(d)
        edges[u].append((v, d))
        edges[v].append((u, d))

    print(solve(n, m, s, t, edges))


if __name__ == '__main__':
    main()