小灵的奇妙上学之旅(Hard)

题目大意

给出一个$N$个结点$M$条边的有向图，并且保证只会存在由前面顶点到达后面的边。求从1号顶点到达$N$号顶点所有的走法。

思路解析

范围由一开始的$n \leq50$开到了$n \leq 1000$，所以暴力枚举肯定行不通，但是我们可以发现一件事，在这个有向图当中，前面的顶点只会前往后面的顶点，那么他是不会返回的。

如果我们计算出了第$i$号顶点的路径总数，那么$pos$号顶点可以前往$pos2$号顶点的话，那么我们是不是可以认为，$pos2$号顶点的方案总数，一定包含$pos$号顶点的方案总数，因此我们就可以列出状态转移方程。

$IF$ $ G[pos][i] == pos2$ $dp[pos2] += dp[pos]$

代码演示

#include<bits/stdc++.h>
using namespace std;
vector<int> G[1005];
int n,k,v;
int answer;
int dp[10005];
int main()
{
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ ){ // 第i号顶点
		cin >> k ; // 一共拥有k条边
		for(int j = 1 ; j <= k ; j ++ ){ // 输入每条边的终点
			cin >> v;
			G[i].push_back(v); // 邻接矩阵存储
		}
	}
	dp[1] = 1;
	for(int i = 1 ; i <= n ; i ++ ){ // 第i号顶点
		for(int j = 0 ; j < G[i].size() ; j ++ ){ // 输入每条边的终点
			int next_pos = G[i][j];
			dp[next_pos] += dp[i];
			dp[next_pos] %=114514;
		}
	}
	
	cout<< dp[n]%114514 << endl;
	
	
	
	return 0;
}