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:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N,M=map(int,input().split())
S,T=map(int,input().split())
mati=Dijkstra(N)
edge=[[] for i in range(N)]
Edge=[]
for i in range(M):
    u,v,d=map(int,input().split())
    mati.add(u-1,v-1,d)
    mati.add(v-1,u-1,d)
    edge[u-1].append((v-1,d))
    edge[v-1].append((u-1,d))
    Edge.append((u-1,v-1,d))
    Edge.append((v-1,u-1,d))

mod=10**9+7

spath=mati.shortest_path(S-1)
tpath=mati.shortest_path(T-1)

Submission status: Wrong Answer

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N,M=map(int,input().split())
S,T=map(int,input().split())
mati=Dijkstra(N)
edge=[[] for i in range(N)]
Edge=[]
for i in range(M):
    u,v,d=map(int,input().split())
    mati.add(u-1,v-1,d)
    mati.add(v-1,u-1,d)
    edge[u-1].append((v-1,d))
    edge[v-1].append((u-1,d))
    Edge.append((u-1,v-1,d))
    Edge.append((v-1,u-1,d))

mod=10**9+7

spath=mati.shortest_path(S-1)
tpath=mati.shortest_path(T-1)

Sways=[-1]*N
Sways[S-1]=1
def Sdfs(v):
    if Sways[v]!=-1:
        return Sways[v]

    ans=0
    for pv,cost in edge[v]:
        if spath[pv]+cost==spath[v]:
            ans+=Sdfs(pv)
            ans%=mod
    Sways[v]=ans
    return Sways[v]

Sways=[Sdfs(i)%mod for i in range(N)]

Tways=[-1]*N
Tways[T-1]=1
def Tdfs(v):
    if Tways[v]!=-1:
        return Tways[v]

    ans=0
    for pv,cost in edge[v]:
        if tpath[pv]+cost==tpath[v]:
            ans+=Tdfs(pv)
            ans%=mod
    Tways[v]=ans
    return Tways[v]

Tways=[Tdfs(i)%mod for i in range(N)]

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()


    n, m = map(int, input().split())
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    from collections import defaultdict
    ns = defaultdict(set)
    for i in range(m):
        u, v, d = map(int, input().split())
        ns[u-1].add((v-1, d))
        ns[v-1].add((u-1, d))
    
    def dijkstra(start):
        import heapq
        h = []
        heapq.heapify(h)
        vals = [None] * n
        nums = [None] * n
        nums[start] = 1
        heapq.heappush(h, (0, start)) # (距離, ノード番号)
        while h:
            val, u = heapq.heappop(h)
            vals[u] = val
            for v, d in ns[u]:
                if vals[v] is None or vals[v]>val+d:
                    vals[v] = val+d
                    nums[v] = nums[u]
                    heapq.heappush(h, (vals[v], v))
                elif vals[v] is not None and vals[v]==val+d:
                    nums[v] = (nums[v] + nums[u]) % M
        return vals, nums
    vals1, nums1 = dijkstra(s)
    vals2, nums2 = dijkstra(t)
    T = vals1[t]

    c1 = 0 # 頂点で衝突するペアの数
    c2 = 0 # エッジ(端点除く)で衝突するペアの数
    
    for u in range(n):
        if vals1[u]==T/2 and vals2[u]==T/2:
            c1 = (c1 + pow((nums1[u] * nums2[u]), 2, M)) % M
        for v,d in ns[u]:
            if (vals1[u]+d+vals2[v]==T) and (2*vals1[u] < T < 2*(vals1[u] + d)):
                c2 = (c2 + ((nums1[u] * nums2[v]))**2) % M
    print((nums1[t]*nums2[s] - (c1+c2)) % M)
hoge()

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


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

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

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

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))



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

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

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

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))

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

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

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

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


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

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

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

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


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

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

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

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

Submission status: Wrong Answer

Solution code:
# ARC090E

def hoge():
    M = 10**9 + 7
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


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

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

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

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

Submission status: Wrong Answer

Solution code:
def getLeftmostBit(n): 
  
    m = 0
    while (n > 1) : 
  
        n = n >> 1
        m += 1
  
    return m 
  
""" 
/* Given the position of previous leftmost 
set bit in n (or an upper bound on 
leftmost position) returns the new 
position of leftmost set bit in n */ 
"""
def getNextLeftmostBit(n, m) : 
  
    temp = 1 << m 
    while (n < temp) : 
        temp = temp >> 1
        m -= 1
  
    return m 
  
# The main recursive function used by countSetBits() 
# def _countSetBits(n, m) 
  
# Returns count of set bits present in 
# all numbers from 1 to n 
def countSetBits(n) : 
  
    # Get the position of leftmost set 
    # bit in n. This will be used as an 
    # upper bound for next set bit function 
    m = getLeftmostBit(n) 
  
    # Use the position 
    return _countSetBits(n, m) 
  
def _countSetBits(n, m) : 
  
    # Base Case: if n is 0, then set bit 
    # count is 0 
    if (n == 0) : 
        return 0
  
    # /* get position of next leftmost set bit */ 
    m = getNextLeftmostBit(n, m) 
  
    # If n is of the form 2^x-1, i.e., if n 
    # is like 1, 3, 7, 15, 31, .. etc, 
    # then we are done. 
    # Since positions are considered starting 
    # from 0, 1 is added to m 
    if (n == (1 << (m + 1)) - 1) : 
        return ((m + 1) * (1 << m)) 
  
    # update n for next recursive call 
    n = n - (1 << m) 
    return (n + 1) + countSetBits(n) + m * (1 << (m - 1)) 
  
# Driver code 
n = 17
print("Total set bit count is", countSetBits(n))

Submission status: Wrong Answer

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

INF = 10**18
mod = 10**9+7
# AOJ GRL_1_A Single Sourse Shortest Path
import heapq as hp

N, M = map(int, input().split())
s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[] for _ in range(N)]
for _ in range(M):
    n, m, d = map(int, input().split())
    graph[n-1].append((d, m-1)) 
    graph[m-1].append((d, n-1)) #無向グラフならこれ使う

def dijkstra(s):
    D = [INF for _ in range(N)] # 頂点iへの最短距離がD[i]
    B = [0]*N
    D[s] = 0
    B[s] = 1
    q = [] # しまっていく優先度付きキュー
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q)
        if D[np] < nd:
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d:
                D[p] = D[np] + d
                B[p] = B[np]
                hp.heappush(q, (D[p], p))
            elif D[p] == D[np] + d:
                B[p] = (B[p] + B[np])%mod
    return D, B

sD, sB = dijkstra(s)
tD, tB = dijkstra(t)

distance = sD[t]

ans = 0
for n in range(N):
    for d, m in graph[n]:
        if sD[n] + d + tD[m] == distance and 2*sD[n] < distance < 2*(sD[n]+d):
            ans = (ans + sB[n]*tB[m])%mod
    if sD[n] + tD[n] == distance and 2*sD[n] == distance:
        ans = (ans + sB[n]*tB[n]) % mod
ans = (sB[t]*tB[s] - ans) % mod
print(ans)

Submission status: Wrong Answer

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

INF = 10**18
mod = 10**9+7
# AOJ GRL_1_A Single Sourse Shortest Path
import heapq as hp

N, M = map(int, input().split())
s, t = map(int, input().split())
s -= 1; t -= 1
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((d, b-1)) 
    graph[b-1].append((d, a-1)) #無向グラフならこれ使う

def dijkstra(s):
    D = [INF for _ in range(N)] # 頂点iへの最短距離がD[i]
    B = [0]*N
    D[s] = 0
    B[s] = 1
    q = [] # しまっていく優先度付きキュー
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
        if D[np] < nd: # 追加した後の残骸は見ない
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
                D[p] = D[np] + d
                B[p] = B[np]
                hp.heappush(q, (D[p], p))
            elif D[p] == D[np] + d:
                B[p] += B[np]
    return D, B

sD, sB = dijkstra(s)
tD, tB = dijkstra(t)

distance = sD[t]

ans = 0
for n in range(N):
    for d, m in graph[n]:
        a, b = n, m
        if sD[a] > sD[b]:
            continue
        if sD[a] + d + tD[b] == distance and 2*sD[a] < distance < 2*(sD[a]+d):
            ans = (ans + sB[a]*tB[b])%mod
    if sD[n] + tD[n] == distance and 2*sD[n] == distance:
        ans = (ans + sB[n]*tB[n]) % mod
ans = (sB[t]*tB[s] - 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]
                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 and dist_t[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 2 * dist_s[i] < min_cost and 2 * dist_s[j] > min_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]
                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 2 * dist_s[i] < min_cost and 2 * dist_s[j] > min_cost :
            ans -= (ptn_s[i] * ptn_t[j]) ** 2
            ans %= MOD
print(ans)