解説をよんでみると実装の方針はあってる

DFSなりの探索アルゴリズムで探索実装せよとのことで、自分が書いたコードも同じ方針。
なので、そこは問題なかった。

実装が配列作りすぎなのが問題だった

書いてたコードが、こんな感じなんだけど、街から到達可能な街をNxNの配列
dp[N+1][N+1]
で管理。
で、この配列への計算を行ったかを
search_zumi[N+1][N+1]
という２次元配列で管理している。

これが遅いということだった。
そもそも、dpに値が入ってるかどうかで見ればsearch_zumiは不要だった。
Pythonはlistへのインデックスでのアクセスが遅く、これを２次元配列x2個で都合4回行っているのが足を引っ張ってTLEが出ていたようだ。

[実行結果]
PyPy3(7.3.0) TLEx1 2210ms
Python(3.8.2) TLEx2 2208ms

search_zumi[N+1][N+1]
を削除したコードだと、PyPy3ではACでるように。

[実行結果]
PyPy3(7.3.0) AC 649ms
Python(3.8.2) TLEx1 2207ms

解説のコードと同じく1次元配列の結果を順繰り足す構成にすると、PythonでもACに。

[実行結果]
PyPy3(7.3.0) AC 424ms
Python(3.8.2) AC 1598ms

僕が、人間にわかりやすい文脈があるコードに寄せたくなるタイプだから、そういうコードを書いてしまったのが敗因だったけれども。
とりあえずロジックあってそうだけど速度不足の場合は、この点が最適化できる点だとわかってよかった。

3776 / 8819 = 42.8%
結構、正解してるなー。
くやしかー。