Submission #8347512

---

Source Code Expand

from heapq import heappop, heappush
MOD = 10**9+7
N,M= map(int,input().split(' '))
S,T= map(int,input().split(' '))
from collections import defaultdict
g = defaultdict(list)

for i in [0]*M:
    u,v,d = list(map(int,input().split(' ')))
    g[u].append((v,d))
    g[v].append((u,d))

def dj(graph,s):
    inf = 10**20
    d = [inf]*(N+1)
    d[s] = 0
    num = [0]*(N+1)
    num[s] = 1
    que = []
    heappush(que,(s,0))
    while que:
        s,dist = heappop(que)
        if d[s] < dist:
            continue
        for t,c in g[s]:
            if d[t] > d[s] + c:
                d[t] = d[s] + c
                num[t] = num[s]
                heappush(que,(t,d[t]))
            elif d[t] == d[s] + c:
                num[t] += num[s]
                num[t] = num[t] % MOD
    return d,num

Sd,Snum = dj(g,S)
Td,Tnum = dj(g,T)
ans = Snum[T] * Tnum[S]
for v in range(1,N+1):
    if Sd[v] == Td[v]:
        ans -= Snum[v] * Tnum[v] * Snum[v] * Tnum[v]
    for t, c in g[v]:
        # S->v->t->T
        if Sd[t] == Sd[v] + c and Td[v] == Td[t] + c:
            if abs(Sd[v] - Td[t]) < c:
                ans -= Snum[v] * Tnum[t] * Tnum[t] * Snum[v]

print(ans)

Submission Info

Judge Result