もし、動物がいないのであれば単純な最短経路問題で、これは dijkstra 法で解くことができます。動物がどのような役割をするか考えましょう。

まず、動物 \(j\) が動ける範囲は以下のようになります。

• 幅 \(x_j\) 以上の道のみを残した時の、広場 \(v_j\) の連結成分 \(C_j\)

よって、計算量を気にしないのであれば \(v_j \to u ~ (u \in C_j)\) に長さ \(0\) の辺を張ればよいです。しかし、これはもちろん \(O(N^2)\) 辺となるため、解けません。

2 回以上同じ動物を使うことはない？

結論から言えば考えなくてよいです。

• $a \to b$ を動物 $j$ に乗って移動
• $b \to b$ をなんらかの手段で移動
• $b \to c$ を動物 $j$ に乗って移動

動物は降りるとその場にとどまることから、複数回乗るのであれば、上のような動き方になります。これは明らかに、直接 $a \to c$ へ向かえば良いです。

---

マージ過程を表す木

• 幅 \(x_j\) 以上の道のみを残した時の、広場 \(v_j\) の連結成分 \(C_j\)

という \(C_j\) の特徴を利用しましょう。突然に感じるかもしれませんが、kruskal 法を考えてみましょう。幅が大きい順にソートして kruskal 法をした時、分かれている連結成分はすべて

• 現在見ている幅 \(x\) 以上の道を残した時の連結成分

となっているはずです。これは今回欲しいものと同じです。よって、これを利用します。

kruskal 法のマージ過程を、次のような木で表します。

• 最初に、各広場に対応する頂点 \(1, \dots ,N\) を用意する。
• 異なる \(2\) つの連結成分 \(u, v\) が道によってつながったら、新しい頂点 \(p\) を作り \(p \to u, p\to v\) と辺を張る。
• 以降は、新しい頂点 \(p\) がマージ後の連結成分を表す。

この木の各頂点は、kruskal 法の途中に現れる連結成分を表します。特に、「幅 \(x_j\) 以上の道をすべて追加した直後に広場 \(v_j\) が属している連結成分」は、動物 \(j\) が動ける範囲 \(C_j\) と一致します。

以降は、上の連結成分を表す頂点を \(p_j\) と呼ぶことにします。つまり、\(C_j\) はこの木における \(p_j\) の部分木の葉集合と一致します。

---

まとめ

ということで、以下のように辺を張れば良いです。

• マージ過程を表す木をつくる
• 親 \(p\) から子 \(u, v\) に向けて重み \(0\) の辺
• 動物に対応する \(v_j \to p_j\) に重み \(0\) の辺
• もとのグラフに存在する \(a_i \to b_i, b_i \to a_i\) の辺

2.3. の辺によって \(v_j \to u ~ (u \in C_j)\) と同じ役割をしていることに注意してください。そして、このグラフ上で最短経路問題を解けば良いです。

dijkstra 法に \(O((N + M + K) \log (N + M + K))\) がかかり、ここが律速です。計算量は \(O(N + M + K \log (N + M + K))\) です。

---

実装例

from atcoder.dsu import DSU
from heapq import heappop, heappush

n, m, k = map(int, input().split())

g = [[] for _ in range(n)]
eve = []

for _ in range(m):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, d))
    g[b].append((a, d))
    eve.append((c, a, b))

for _ in range(k):
    v, x = map(int, input().split())
    v -= 1
    eve.append((x, -1, v))

eve.sort(reverse=True)

uf = DSU(n)
node = list(range(n))

for _, a, b in eve:
    if a != -1:
        a = uf.leader(a)
        b = uf.leader(b)
        
        if a == b: continue
        
        g.append([(node[a], 0), (node[b], 0)])
        node[uf.merge(a, b)] = len(g) - 1
    else:
        r = uf.leader(b)
        g[b].append((node[r], 0))

inf = 10 ** 18
dis = [inf] * len(g)
dis[0] = 0

que = [(0, 0)]

while que:
    d, u = heappop(que)
    if d != dis[u]: continue
    for v, w in g[u]:
        if d + w < dis[v]:
            dis[v] = d + w
            heappush(que, (d + w, v))

print(dis[n-1])