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

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

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
class RadixHeap:
    # from https://ikatakos.com/pot/programming_algorithm/data_structure/radix_heap
    v = [[] for _ in range(70)]

    def __init__(self):
        self.last = 0

    def push(self, x):
        self.v[(x ^ self.last).bit_length()].append(x)

    def pop(self):
        if not self.v[0]:
            cv = next(x for x in self.v if x)
            self.last = min(cv)
            for x in cv:
                self.push(x)
            cv.clear()
        return self.v[0].pop()


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

    def dijksrtra(start):
        Dist = [INF] * (N+1)
        Dist[start] = 0
        #q = [0<<20 | start]
        q = RadixHeap()
        q.push(1<<68)  # 番兵
        q.push(0<<20 | start)
        mask = (1<<20)-1
        while True:
            #dist_v = heappop(q)
            dist_v = q.pop()
            if dist_v == 1<<68:
                break
            v = dist_v & mask
            dist = dist_v >> 20
            if Dist[v] != dist:
                continue
            for u, d in E[v]:
                new_dist = dist + d
                if Dist[u] > new_dist:
                    Dist[u] = new_dist
                    #heappush(q, new_dist<<20 | u)
                    q.push(new_dist<<20 | u)
        return Dist

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

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

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

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

    ans = ans * ans % mod

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(500000)
    input = sys.stdin.readline
    from heapq import heappop, heappush
    mod = 10**9+7
    INF = 1<<60
    N, M = map(int, input().split())
    S, T = map(int, input().split())
    E = [[] for _ in range(N+1)]
    edges = []
    for _ in range(M):
        u, v, d = map(int, input().split())
        E[u].append((v, d))
        E[v].append((u, d))
        edges.append((u, v, d))
    
    def dijksrtra(start):
        Dist = [INF] * (N+1)
        Dist[start] = 0
        q = [0<<20 | start]
        mask = (1<<20)-1
        while q:
            dist_v = heappop(q)
            v = dist_v & mask
            dist = dist_v >> 20
            if Dist[v] != dist:
                continue
            for u, d in E[v]:
                new_dist = dist + d
                if Dist[u] > new_dist:
                    Dist[u] = new_dist
                    heappush(q, new_dist<<20 | u)
        return Dist
    
    Dist_S = dijksrtra(S)
    Dist_T = dijksrtra(T)
    dist_st = Dist_S[T]
    
    DAG_edges = []  # S -> T
    DAG = [[] for _ in range(N+1)]
    DAG_rev = [[] for _ in range(N+1)]
    for u, v, d in edges:
        if Dist_S[u] + Dist_T[v] + d == dist_st:
            DAG_edges.append((u, v))
            DAG[u].append(v)
            DAG_rev[v].append(u)
        elif Dist_T[u] + Dist_S[v] + d == dist_st:
            DAG_edges.append((v, u))
            DAG[v].append(u)
            DAG_rev[u].append(v)
    
    n_paths_S = [-1] * (N+1)
    n_paths_T = [-1] * (N+1)
    n_paths_S[S] = 1
    n_paths_T[T] = 1
    def calc_n_paths_S(v):
        if n_paths_S[v] != -1:
            return n_paths_S[v]
        res = 0
        for u in DAG_rev[v]:
            res = (res + calc_n_paths_S(u)) % mod
        n_paths_S[v] = res
        return res
    def calc_n_paths_T(v):
        if n_paths_T[v] != -1:
            return n_paths_T[v]
        res = 0
        for u in DAG[v]:
            res = (res + calc_n_paths_T(u)) % mod
        n_paths_T[v] = res
        return res
    
    ans = calc_n_paths_S(T)  # 全経路数
    calc_n_paths_T(S)
    
    ans = ans * ans % mod
    
    for v, u in DAG_edges:  # 辺ですれ違う場合
        if Dist_S[v]*2 < dist_st and dist_st < Dist_S[u]*2:
            ans = (ans - (n_paths_S[v]*n_paths_T[u])**2) % mod
    
    # 頂点ですれ違う場合
    for v, (dist, ns, nt) in enumerate(zip(Dist_S, n_paths_S, n_paths_T)):
        if dist*2 == dist_st:
            ans = (ans - (ns*nt)**2) % mod
    
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
# heapq の中身を 1 つに
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
from heapq import heappop, heappush
mod = 10**9+7
INF = 1<<60
N, M = map(int, input().split())
S, T = map(int, input().split())
E = [[] for _ in range(N+1)]
edges = []
for _ in range(M):
    u, v, d = map(int, input().split())
    E[u].append((v, d))
    E[v].append((u, d))
    edges.append((u, v, d))

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

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

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

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

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

ans = ans * ans % mod

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

ans = ans * ans % mod

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

ans = calc_n_paths_S(T)  # 全経路数
assert ans == calc_n_paths_T(S), (n_paths_S, n_paths_T)

ans = ans * ans % mod

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(500000)
    input = sys.stdin.readline
    from heapq import heappop, heappush
    mod = 10**9+7
    INF = 1<<60
    N, M = map(int, input().split())
    S, T = map(int, input().split())
    E = [[] for _ in range(N+1)]
    edges = []
    for _ in range(M):
        u, v, d = map(int, input().split())
        E[u].append((v, d))
        E[v].append((u, d))
        edges.append((u, v, d))
    
    def dijksrtra(start):
        Dist = [INF] * (N+1)
        Dist[start] = 0
        q = [(0, start)]
        while q:
            dist, v = heappop(q)
            if Dist[v] != dist:
                continue
            for u, d in E[v]:
                new_dist = dist + d
                if Dist[u] > new_dist:
                    Dist[u] = new_dist
                    heappush(q, (new_dist, u))
        return Dist
    
    Dist_S = dijksrtra(S)
    Dist_T = dijksrtra(T)
    dist_st = Dist_S[T]
    
    DAG_edges = []  # S -> T
    DAG = [[] for _ in range(N+1)]
    DAG_rev = [[] for _ in range(N+1)]
    for u, v, d in edges:
        if Dist_S[u] + Dist_T[v] + d == dist_st:
            DAG_edges.append((u, v, d))
            DAG[u].append((v, d))
            DAG_rev[v].append((u, d))
        elif Dist_T[u] + Dist_S[v] + d == dist_st:
            DAG_edges.append((v, u, d))
            DAG[v].append((u, d))
            DAG_rev[u].append((v, d))
    
    n_paths_S = [-1] * (N+1)
    n_paths_T = [-1] * (N+1)
    n_paths_S[S] = 1
    n_paths_T[T] = 1
    def calc_n_paths_S(v):
        if n_paths_S[v] != -1:
            return n_paths_S[v]
        res = 0
        for u, _ in DAG_rev[v]:
            res = (res + calc_n_paths_S(u)) % mod
        n_paths_S[v] = res
        return res
    def calc_n_paths_T(v):
        if n_paths_T[v] != -1:
            return n_paths_T[v]
        res = 0
        for u, _ in DAG[v]:
            res = (res + calc_n_paths_T(u)) % mod
        n_paths_T[v] = res
        return res
    
    ans = calc_n_paths_S(T)  # 全経路数
    assert ans == calc_n_paths_T(S), (n_paths_S, n_paths_T)
    
    ans = ans * ans % mod
    
    for v, u, _ in DAG_edges:  # 辺ですれ違う場合
        if Dist_S[v]*2 < dist_st and dist_st < Dist_S[u]*2:
            ans = (ans - (n_paths_S[v]*n_paths_T[u])**2) % mod
    
    # 頂点ですれ違う場合
    for v, (dist, ns, nt) in enumerate(zip(Dist_S, n_paths_S, n_paths_T)):
        if dist*2 == dist_st:
            ans = (ans - (ns*nt)**2) % mod
    
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

ans = calc_n_paths_S(T)  # 全経路数
assert ans == calc_n_paths_T(S), (n_paths_S, n_paths_T)

ans = ans * ans % mod

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

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

print(ans)