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: Wrong Answer

Solution code:
# 参考: https://qiita.com/y-tsutsu/items/aa7e8e809d6ac167d6a1

from heapq import heappush, heappop


# 多次元配列
# dp = [[0] * 3 for _ in range(5)


class Edge:
    def __init__(self, to: int, cost: int):
        self._to = to
        self._cost = cost

    @property
    def to(self):
        return self._to

    @property
    def cost(self):
        return self._cost


class Edges(list):
    def __init__(self):
        list.__init__(self)


INF = 1 << 28
MOD = int(1e9) + 7


def dijkstra(graph, s: int):
    n = len(graph)
    dist = [INF for _ in range(n)]
    cnts = [0 for _ in range(n)]

    pq = []
    heappush(pq, (0, s))
    dist[s] = 0
    cnts[s] = 1

    while pq:
        (cost, cur) = heappop(pq)

        if dist[cur] != cost:
            continue

        for next in graph[cur]:
            if dist[next.to] > cost + next.cost:
                heappush(pq, (cost + next.cost, next.to))
                dist[next.to] = cost + next.cost
                cnts[next.to] = cnts[cur]
            elif dist[next.to] == cost + next.cost:
                cnts[next.to] = (cnts[next.to] + cnts[cur]) % MOD

    return dist, cnts


# 入力を受け取る
n, m = map(int, input().split())

s, t = map(lambda i: int(i) - 1, input().split())

g = [Edges() for _ in range(n)]

for _ in range(m):
    u, v, d = map(int, input().split())
    g[u - 1].append(Edge(v - 1, d))
    g[v - 1].append(Edge(u - 1, d))

dst1, cnt1 = dijkstra(g, s)
dst2, cnt2 = dijkstra(g, t)

ret = cnt1[t] * cnt1[t] % MOD

for i in range(n):
    if 2 * dst1[i] == dst1[t]:
        sub = cnt1[i] * cnt1[i] % MOD
        sub = sub * cnt2[i] % MOD * cnt2[i] % MOD
        ret = (ret + MOD - sub) % MOD

sum_sub = 0
for u in range(n):
    for e in g[u]:
        v, d = e.to, e.cost
        if 2 * dst1[u] < dst1[t] < 2 * dst1[v] and dst1[u] + d == dst1[v] and dst2[v] + d == dst2[u]:
            sub = cnt1[u] * cnt1[u] % MOD
            sub = sub * cnt2[v] % MOD * cnt2[v] % MOD
            sum_sub = (sum_sub + sub) % MOD

ret = (ret + MOD - sum_sub) % MOD
print(ret)

Submission status: Wrong Answer

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, (cost[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: Wrong Answer

Solution code:
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 = [T]
while Q:
    p = Q.pop()
    for q, d in G[p]:
        if cost[p] - d != cost[q]:
            continue
        if cost[q] <= (2*end - cost[q] - cost[p])/2 < cost[p]:
            ans = (ans - appear[q])%MOD
        Q.append(q)
print(ans)

Submission status: Wrong Answer

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)

n_par = [0] * (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_)
    n_par[from_] += 1

    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]

cnt_T = [0] * (N+1)
cnt_T[T] = 1
q = [T]
while len(q)!=0:
    v = q.pop()
    cnt = cnt_T[v]
    for u in E_S[v]:
        cnt_T[u] += cnt
        n_par_ = n_par[u] - 1
        if n_par_ == 0:
            q.append(u)
        n_par[u] = n_par_
        
ans = cnt_st * cnt_st

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

Submission status: Wrong Answer

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:
				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: Wrong Answer

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)
		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:
				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: Wrong Answer

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)
		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:
				continue
			if SI*2 < goal < SJ*2:
				#print(i, j, SI, SJ)
				ans -= 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)
				ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

mod = 10 ** 9 + 7

n, m = map(int, input().split())

s, t = map(int, input().split())

uvds = [tuple(map(int, input().split())) for _ in range(m)]

links = defaultdict(dict)
for uvd in uvds:
    u, v, d = uvd
    if v in links[u]:
        links[u][v] = (d, links[u][v][1] + 1)
    else:
        links[u][v] = (d, 1)

    if u in links[v]:
        links[v][u] = (d, links[v][u][1] + 1)
    else:
        links[v][u] = (d, 1)

links[-1][s] = (0, 1)
links[-1][t] = (0, 1)

def dijkstra(start):
    distances_and_patterns = defaultdict(lambda: (10**17, 0))
    distances_and_patterns[-1] = (0, 1)
    q = [(0, start, -1)]
    while len(q) != 0:
        current_distance, current, from_ = heapq.heappop(q)
        from_distance, from_pattern = distances_and_patterns[from_]
        past_distance, past_pattern = distances_and_patterns[current]
        #print(current_distance, current, from_, distances_and_patterns)
        if current_distance < past_distance:
            distances_and_patterns[current] = (current_distance, from_pattern * links[from_][current][1])
            for next_ in links[current]:
                next_distance = current_distance + links[current][next_][0]
                if next_distance <= distances_and_patterns[next_][0]:
                    heapq.heappush(q, (next_distance, next_, current))
        elif current_distance == past_distance:
            distances_and_patterns[current] = (current_distance, (past_pattern + from_pattern * links[from_][current][1]) % mod)

    #print(current_distance, current, from_, distances_and_patterns)
    return distances_and_patterns

s_distances_and_patterns = dijkstra(s)
t_distances_and_patterns = dijkstra(t)

s_t_distance, s_t_pattern = s_distances_and_patterns[t]

ans = (s_t_pattern * s_t_pattern) % mod

for uvd in uvds:
    u, v, d = uvd
    s_u_distance, s_u_pattern = s_distances_and_patterns[u]
    s_v_distance, s_v_pattern = s_distances_and_patterns[v]
    t_u_distance, t_u_pattern = t_distances_and_patterns[u]
    t_v_distance, t_v_pattern = t_distances_and_patterns[v]

    u_nearer_distance = min(s_u_distance, t_u_distance)
    v_nearer_distance = min(s_v_distance, t_v_distance)

    if u_nearer_distance < s_t_distance // 2 and v_nearer_distance < s_t_distance // 2 and u_nearer_distance + d + v_nearer_distance == s_t_distance:
        p = 1
        if s_u_distance < t_u_distance:
            p *= s_u_pattern
        else:
            p *= t_u_pattern
        if s_v_distance < t_v_distance:
            p *= s_v_pattern
        else:
            p *= t_v_pattern

        ans = (ans - p) % mod

for i in range(1, n+1):
    s_i_distance, s_i_pattern = s_distances_and_patterns[i]
    t_i_distance, t_i_pattern = t_distances_and_patterns[i]

    if s_i_distance == t_i_distance:
        ans = (ans - s_i_pattern * t_i_pattern) % mod

#print(s_distances_and_patterns)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

mod = 10 ** 9 + 7

n, m = map(int, input().split())

s, t = map(int, input().split())

uvds = [tuple(map(int, input().split())) for _ in range(m)]

links = defaultdict(dict)
for uvd in uvds:
    u, v, d = uvd
    links[u][v] = d
    links[v][u] = d

def dijkstra(start):
    distances_and_patterns = defaultdict(lambda: (10**17, 0))
    distances_and_patterns[-1] = (0, 1)
    q = [(0, start, -1)]
    while len(q) != 0:
        current_distance, current, from_ = heapq.heappop(q)
        from_distance, from_pattern = distances_and_patterns[from_]
        past_distance, past_pattern = distances_and_patterns[current]
        if current_distance < past_distance:
            distances_and_patterns[current] = (current_distance, from_pattern)
            for next_ in links[current]:
                next_distance = current_distance + links[current][next_]
                if next_distance <= distances_and_patterns[next_][0]:
                    heapq.heappush(q, (next_distance, next_, current))
        elif current_distance == past_distance:
            distances_and_patterns[current] = (current_distance, (past_pattern + from_pattern) % mod)

    return distances_and_patterns

s_distances_and_patterns = dijkstra(s)
t_distances_and_patterns = dijkstra(t)

s_t_distance, s_t_pattern = s_distances_and_patterns[t]

ans = (s_t_pattern * s_t_pattern) % mod

for uvd in uvds:
    u, v, d = uvd
    s_u_distance, s_u_pattern = s_distances_and_patterns[u]
    s_v_distance, s_v_pattern = s_distances_and_patterns[v]
    t_u_distance, t_u_pattern = t_distances_and_patterns[u]
    t_v_distance, t_v_pattern = t_distances_and_patterns[v]

    u_nearer_distance = min(s_u_distance, t_u_distance)
    v_nearer_distance = min(s_v_distance, t_v_distance)

    if u_nearer_distance < s_t_distance // 2 and v_nearer_distance < s_t_distance // 2 and u_nearer_distance + d + v_nearer_distance == s_t_distance:
        p = 1
        if s_u_distance < t_u_distance:
            p *= s_u_pattern
        else:
            p *= t_u_pattern
        if s_v_distance < t_v_distance:
            p *= s_v_pattern
        else:
            p *= t_v_pattern

        ans = (ans - p) % mod

for i in range(1, n+1):
    s_i_distance, s_i_pattern = s_distances_and_patterns[i]
    t_i_distance, t_i_pattern = t_distances_and_patterns[i]

    if s_i_distance == t_i_distance:
        ans = (ans - s_i_pattern * t_i_pattern) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

mod = 10 ** 9 + 7

n, m = map(int, input().split())

s, t = map(int, input().split())

uvds = [tuple(map(int, input().split())) for _ in range(m)]

links = defaultdict(dict)
for uvd in uvds:
    u, v, d = uvd
    links[u][v] = d
    links[v][u] = d

def dijkstra(start):
    distances_and_patterns = defaultdict(lambda: (10**17, 0))
    distances_and_patterns[start] = (0, 1)
    q = []
    heapq.heapify(q)
    for next_ in links[start]:
        heapq.heappush(q, (links[start][next_], next_, start))
    while len(q) != 0:
        distance, current, from_ = heapq.heappop(q)
        if distance < distances_and_patterns[current][0]:
            distances_and_patterns[current] = (distance, distances_and_patterns[from_][1])
            for next_ in links[current]:
                heapq.heappush(q, (distance + links[current][next_], next_, current))
        elif distance == distances_and_patterns[current][0]:
            _, past_pattern = distances_and_patterns[current]
            distances_and_patterns[current] = (distance, (past_pattern + distances_and_patterns[from_][1]) % mod)

    return distances_and_patterns

s_distances_and_patterns = dijkstra(s)
t_distances_and_patterns = dijkstra(t)

s_t_distance, s_t_pattern = s_distances_and_patterns[t]

ans = (s_t_pattern * s_t_pattern) % mod

for uvd in uvds:
    u, v, d = uvd
    s_u_distance, s_u_pattern = s_distances_and_patterns[u]
    s_v_distance, s_v_pattern = s_distances_and_patterns[v]
    t_u_distance, t_u_pattern = t_distances_and_patterns[u]
    t_v_distance, t_v_pattern = t_distances_and_patterns[v]

    u_nearer_distance = min(s_u_distance, t_u_distance)
    v_nearer_distance = min(s_v_distance, t_v_distance)

    if u_nearer_distance < s_t_distance // 2 and v_nearer_distance < s_t_distance // 2 and u_nearer_distance + d + v_nearer_distance == s_t_distance:
        p = 1
        if s_u_distance < t_u_distance:
            p *= s_u_pattern
        else:
            p *= t_u_pattern
        if s_v_distance < t_v_distance:
            p *= s_v_pattern
        else:
            p *= t_v_pattern

        ans = (ans - p) % mod

for i in range(1, n+1):
    s_i_distance, s_i_pattern = s_distances_and_patterns[i]
    t_i_distance, t_i_pattern = t_distances_and_patterns[i]

    if s_i_distance == t_i_distance:
        ans = (ans - s_i_pattern * t_i_pattern) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
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

cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
print
D=cost_S[T-1]
Pat=P_S[T-1]
ans=Pat**2
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
for i in range(N):
  if 2*cost_S[i]==2*cost_T[i]==D:
    ans-=(P_S[i]*P_T[i])**2
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
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(N):
  Edge.append((i,i,0))
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
  Visited[s]=True
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    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
      else:
        Visited[p]=True
    Visited[hp]=True
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
D=cost_S[T-1]
List=[]
for a,b,c in Edge:
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]<D/2 and cost_T[b]<D/2 and c>0:
    List.append((P_S[a]*P_T[b])%mod)
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]==D/2 and cost_T[b]==D/2 and c==0:
    List.append((P_S[a]*P_T[b])%mod)
Sum=0
for i in List:
  Sum=(Sum+i)%mod
ans=0
for i,c in enumerate(List):
  ans=(ans+(Sum-List[i])*List[i])%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
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(N):
  Edge.append((i,i,0))
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
  Visited[0]=True
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    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
      if c+hc>cost[p]:
        Visited[p]=True
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
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(N):
  Edge.append((i,i,0))
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
  Visited[0]=True
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    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
      if c+hc>cost[p]:
        Visited[p]=True
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
D=cost_S[T-1]
List=[]
for a,b,c in Edge:
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]<D/2 and cost_T[b]<D/2 and c>0:
    List.append((P_S[a]*P_T[b])%mod)
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]==D/2 and cost_T[b]==D/2 and c==0:
    List.append((P_S[a]*P_T[b])%mod)
Sum=0
for i in List:
  Sum=(Sum+i)%mod
ans=0
for i,c in enumerate(List):
  ans=(ans+(Sum-List[i])*List[i])%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify,heappop,heappush
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(N):
  Edge.append((i,i,0))
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
  Visited[0]=True
  cost=[inf]*n
  P=[0]*n
  P[s]=1
  cost[s]=0
  heap=[(0,s)]
  heapify(heap)
  while heap:
    hc,hp=heappop(heap)
    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[hp]
      if c+hc>cost[p]:
        Visited[p]=True
  return cost,P
  
cost_S,P_S=dijkstra(S-1,N,Graph)
cost_T,P_T=dijkstra(T-1,N,Graph)
D=cost_S[T-1]
List=[]
for a,b,c in Edge:
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]<D/2 and cost_T[b]<D/2 and c>0:
    List.append(P_S[a]*P_T[b]%mod)
  if cost_S[a]+c+cost_T[b]==D and cost_S[a]==D/2 and cost_T[b]==D/2 and c==0:
    List.append(P_S[a]*P_T[b]%mod)
Sum=sum(List)%mod
ans=0
for i,c in enumerate(List):
  ans=(ans+(Sum-List[i])*List[i])%mod
print(ans-1)

Submission status: Wrong Answer

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

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

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


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

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

            uc = d[u][1]

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

        return d

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

    r = d1[t][1] ** 2
    for k in list(d1.keys()):
        t,c = d1[k]
        if t > kk:
            continue
        if t == kk:
            if d2[k][0] == t:
                r -= c**2 * d2[k][1]**2
            continue

        for uv, ud in e[k]:
            if d2[uv][0] >= kk or t + ud + d2[uv][0] != rd:
                continue
            r -= c**2 * d2[uv][1]**2

    return r




print(main())