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:
import heapq
import sys
input = sys.stdin.readline


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]
                pattern[next_pos] %= MOD
            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]) ** 2
        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]) ** 2
            ans %= MOD
print(ans)

Submission status: Wrong Answer

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


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
            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] * 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] * ptn_s[i] * ptn_t[j]
            ans %= MOD
print(ans)

Submission status: Wrong Answer

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


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

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    collision_T = dist[t] / 2 if dist[t] % 2 == 1 else dist[t] // 2
    route = [0] * (N+1)
    route[t] = 1
    que = []
    heapq.heappush(que, (-dist[t], t))
    col_edge = []
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.append((u, v))
                elif dist[v] == collision_T:
                    col_edge.append((v, v))
                if not seen[u]:
                    heapq.heappush(que, (-dist[u], u))
                    seen[u] = 1

    #reverse
    route2 = [0] * (N+1)
    route2[s] = 1
    que = []
    heapq.heappush(que, (0, s))
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    heapq.heappush(que, (dist[u], u))
                    seen[u] = 1

    #print(route)
    #print(route2)

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        assert route[v] != 0
        assert route2[u] != 0
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    collision_T = dist[t] / 2 if dist[t] % 2 == 1 else dist[t] // 2 
    route = [0] * (N+1)
    route[t] = 1
    que = []
    heapq.heappush(que, (-dist[t], t))
    col_edge = []
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.append((u, v))
                elif dist[v] == collision_T:
                    col_edge.append((v, v))
                if not seen[u]:
                    heapq.heappush(que, (-dist[u], u))
                    seen[u] = 1

    #reverse
    route2 = [0] * (N+1)
    route2[s] = 1
    que = []
    heapq.heappush(que, (0, s))
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    heapq.heappush(que, (dist[u], u))
                    seen[u] = 1

    #print(route)
    #print(route2)

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist

def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    T = dist[t]
    collision_T = T / 2
    route = [0] * (N+1)
    route[t] = 1
    que = []
    heapq.heappush(que, (-dist[t], t))
    col_edge = []
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.append((u, v))
                elif dist[v] == collision_T:
                    col_edge.append((v, v))
                if not seen[u]:
                    heapq.heappush(que, (-dist[u], u))
                    seen[u] = 1

    #reverse
    route2 = [0] * (N+1)
    route2[s] = 1
    que = []
    heapq.heappush(que, (0, s))
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    heapq.heappush(que, (dist[u], u))
                    seen[u] = 1

    #print(route)
    #print(route2)

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist

def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    T = dist[t]
    collision_T = T / 2
    route = [0] * (N+1)
    route[t] = 1
    que = []
    heapq.heappush(que, (-dist[t], t))
    col_edge = []
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.append((u, v))
                elif dist[u] == collision_T:
                    col_edge.append((u, u))
                if not seen[u]:
                    heapq.heappush(que, (-dist[u], u))
                    seen[u] = 1

    #reverse
    route2 = [0] * (N+1)
    route2[s] = 1
    que = []
    heapq.heappush(que, (0, s))
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        _, v = heapq.heappop(que)
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    heapq.heappush(que, (dist[u], u))
                    seen[u] = 1

    #print(route)
    #print(route2)
    if route[s] != route2[t]:
        assert False

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist

def main():
    mod = 10**9+7
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        adj[l].append((r, d))
        adj[r].append((l, d))

    dist = dijkstra(adj, s)
    T = dist[t]
    collision_T = T / 2
    route = [0] * (N+1)
    route[t] = 1
    que = deque()
    que.append(t)
    col_edge = []
    seen = [0] * (N+1)
    seen[t] = 1
    while que:
        v = que.popleft()
        for u, d in adj[v]:
            if dist[v] == dist[u] + d:
                route[u] = (route[u] + route[v]) % mod
                if dist[u] < collision_T < dist[v]:
                    col_edge.append((u, v))
                elif dist[u] == collision_T:
                    col_edge.append((u, u))
                if not seen[u]:
                    que.append(u)
                    seen[u] = 1

    #reverse
    route2 = [0] * (N+1)
    route2[s] = 1
    que = deque()
    que.append(s)
    seen = [0] * (N+1)
    seen[s] = 1
    while que:
        v = que.popleft()
        for u, d in adj[v]:
            if dist[u] == dist[v] + d:
                route2[u] = (route2[u] + route2[v]) % mod
                if not seen[u]:
                    que.append(u)
                    seen[u] = 1

    ans = pow(route[s], 2, mod)
    for u, v in col_edge:
        tmp = (route[v] * route2[u])%mod
        ans = (ans - pow(tmp, 2, mod))%mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
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]
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=num_t[v]*num_s[v]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
inf = 10**18
mod = 10**9+7
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    num = [0]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    num[s] = 1
    for e in G[s]:
        heapq.heappush(edges, (e[0], e[1], s))
    while edges:
        cost, v, p = heapq.heappop(edges)
        if dist[v] == cost:
            num[v]+=num[p]
        if dist[v] != inf:
            continue
        dist[v] = cost
        num[v]+=num[p]
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv, v))
    return num, 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)

Submission status: Wrong Answer

Solution code:
import heapq
inf = 10**18
mod = 10**9+7
def dijkstra(s, n, G):#スタート, 頂点数, グラフ:[[(cost, v)], ...]
    dist = [inf]*n
    num = [0]*n
    edges = []#(sからvまでのコストの候補, v)
    dist[s] = 0
    num[s] = 1
    for e in G[s]:
        heapq.heappush(edges, (e[0], e[1], s))
    while edges:
        cost, v, p = heapq.heappop(edges)
        if dist[v] == cost:
            num[v]+=num[p]
        if dist[v] != inf:
            continue
        dist[v] = cost
        num[v]+=num[p]
        for c, nv in G[v]:
            if dist[nv] == inf:
                heapq.heappush(edges, (cost + c, nv, v))
    return num, 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]<l/2<dist_s[v] and dist_s[u]+dist_t[v]+d == l:
        ans-=num_s[u]*num_t[v]
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=num_t[v]*num_s[v]
print(ans)

Submission status: Wrong Answer

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

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
    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 = 32
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 st%2 == 0 and st//2 == dists[i] == distt[i]:
        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 dists[i] < st/2 and distt[vf] < st/2:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)

Submission status: Wrong Answer

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
    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 = 32
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 dists[i] == distt[i]:
        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 dists[i] < st/2 and distt[vf] < st/2:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)

Submission status: Wrong Answer

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

from heapq import heappop as hpp, heappush as hp
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
    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 = 32
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]
oset = set(onpath)

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]:
        cost = k>>geta
        vf = k^(cost<<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)