Submission #6216928

---

Source Code Expand

import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse import *

N,M,R,T = map(int,input().split())
ABC = np.array([input().split() for _ in range(M)], dtype = np.int64)

A = ABC[:,0]
B = ABC[:,1]
C = ABC[:,2]
graph = csr_matrix((C,(A,B)),(N+1,N+1))

dist_mat = csgraph.dijkstra(graph, directed = False).astype(np.int64)

dist_mat = dist_mat[1:,1:]

# 目的地を固定する
# 距離順にソート
# 各うさぎに対して、カメを数える
# 互いに異なるように注意する

answer = 0
for a in range(N):
    dist = dist_mat[a]
    dist.sort()
    dist = dist[1:] # a自身を除外
    # R * b > T * c となるb,c
    cnt = np.searchsorted(R*dist, T*dist, side = 'left')
    answer += cnt.sum()
    
# b == c を除外
if T > R:
    answer -= N*(N-1)

print(answer)

Submission Info

Judge Result