イベント \(0\) を，時刻 \(0\) で地点 \(1\) に開催されるイベントとします．イベント \(0\) には必ず参加できます． また，あらかじめイベントを時刻 \(t_i\) によってソートしておき， \(t_0\leq t_1 \leq \dots \leq t_K\) とします．

動的計画法を考えます．\(\mathrm{dp}[i]\) を，イベント \(i\) に参加するとしたとき，それより前に参加できるイベントの最大数とします．\(\mathrm{dp}[0]=0, \mathrm{dp}[i]=-\infty \, (i \geq 1)\) で初期化します．

\(1 \leq i < j \leq K\) について，イベント \(i\) に参加した後にイベント \(j\) に参加できるための条件は，地点 \(c_i\) から地点 \(c_j\) に \(t_j-t_i\) 分以内の時間で到達できることです．よって，地点 \(c_i\) から各地点へ到達するための最短時間をダイクストラ法によって求めることで，各 \(j > i\) についてイベント \(j\) に参加できるかどうかが判定できます．イベント \(i\) のあとにイベント \(j\) に参加できるとき， \(\mathrm{dp}[j] \leftarrow \max\{\mathrm{dp}[j], \mathrm{dp}[i] + 1\}\) と更新します．

ダイクストラ法1回の時間計算量は \(O(M \log N)\) です．各 \(c_i\) を始点としてダイクストラ法を実行する必要があるため，全体の時間計算量は \(O(KM \log N)\) となります．

実装例

def dijkstra(G, s):
    from heapq import heappush, heappop

    INF = 10**18
    dist = [INF] * len(G)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, v = heappop(pq)
        if d > dist[v]:
            continue
        for u, weight in G[v]:
            nd = d + weight
            if dist[u] > nd:
                dist[u] = nd
                heappush(pq, (nd, u))
    return dist


N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, d))
    G[b].append((a, d))

events = [(0, 0)]
for _ in range(K):
    c, t = map(int, input().split())
    events.append((c - 1, t))
events.sort(key=lambda p: p[1])

dp = [-(10**9)] * (K + 1)
dp[0] = 0
for i, (ci, ti) in enumerate(events):
    dist = dijkstra(G, ci)
    for j in range(i + 1, K + 1):
        cj, tj = events[j]
        if ti + dist[cj] < tj:
            dp[j] = max(dp[j], dp[i] + 1)
print(max(dp))