luogu3953

题目描述

给定一个有向图，求从到路径长度不超过最短路+的路径条数。

解题思路

首先考虑DAG，DAG只需要建反图跑dp及可。具体就是设表示当前节点为，路径长度超过的长度为的路径条数。

接下来考虑正环。注意到正环的处理过程中是单调递减的，因此处理方式不变。

接下来考虑零环。当出现零环的时候，答案有可能是正无穷。

首先我们考虑一下怎么判断出现零环。我们可以判断当前的状态在搜索栈中是否出现过，出现过即代表有零环。这只需要通过一个简单的即可实现。

接下来判断零环是否对答案有贡献。假设当前的查找路径长度为，判断标准为。利用极端原理来判断。

本题作为NOIP2017的D1T3，解法显得清晰自然。它体现了图论问题解决的一种范式，即从DAG出发，深入到正环、零环、负环，最终解决问题。在解决问题的途中，还要注意特殊点对答案的影响。