AC 7 （再加上一个 hack 数据），WA 3 ，含有 0 边的测试点都错了。
蒟蒻表示既不确定为什么对了，也不知道为什么错了...

我的想法是：记单源最短路 $dist[i]$ ，单汇最短路 $tsid[i]$ ，最短路 $d=dist[N]$ ；记 $f[i][j]$ 表示 当前在节点 $i$ ，已走路程加上至少还需走的路程比 $d$ 多 $j$ 的方案数。即，设当前已走 $s$ ，有 $s + tsid[i] = d + j$ 我不太清楚这么设定的道理在哪，感性理解大概是“还有距离 $j$ 可以浪”的样子qwq；或者干脆就当成某种定义好的“状态”吧，且仅有 $0\leq j \leq K$ （$K$ 含义如题）的状态的节点有机会被统计...
按这个理解的话，答案就是 $\Sigma^{K}_{j=0} f[N][j]$
然后对于每个节点 $i$ ，其状态 $j$ ：
当 $j < dist[i]+tsid[i]-d$ 时 $f[i][j]=0$，
当 $j = dist[i]+tsid[i]-d$ 时 $f[i][j]=sum[i]$ ，$sum[i]$ 表示从起点走到 $i$ 的最短路径数，
当 $j > dist[i]+tsid[i]-d$ 时考虑用递推。

我们考虑一条边 $u$ -> $v$ ，边权 $w$ ， $u$ 和 $v$ 各自的状态分别是 $p$ 、 $q$ ，则有 $s + tsid[u] = d + p$ , $s + w + tsid[v] = d + q$ ，联立下就有 $p + (w + tsid[v] - tsid[u]) = q$ ，因为括号里的东西是不为负的，干脆替换成 $w'$ 搞一个新图；由上，对于任意一条有向边 $u$ -> $v$ ，前者的状态值小等于后者，按这个性质就能跑记搜了。

那什么时候发现有无穷条路线呢？因为跑记搜时调用的状态值仅仅是不减的，那如果跑到当前还在搜索栈里的点，就会无限累加下去，这时就能退出了。

AC 7 （再加上一个 hack 数据），WA 3 ，含有 0 边的测试点都错了。下了个测试点，应该是统计部分出错了。然而蒟蒻连怎么对的都不确定，更不知道为什么错了...（从上面的推导中看不出零边特殊在哪）但感觉至少判断是否有无穷条路线以及不含零边的部分能过，应该还是有点道理的做法吧（小声）

求教qwq