题意:

题意有点抽象,翻译一下n个点,m条边,求1号点有多少种方式到达n号点

做法:

实际上就是求一个拓扑序,首先将入度为0的点入队,然后在遍历的同时,判断是否新增了入度为0的点即可。对于每个分支,都增加当前点的方法数,最后答案就是n号点的值

代码:

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
const ll mod = 20010905;
struct edge
{
	int to;
	ll w;
	int nex;
}e[MAXN * 4];
int head[MAXN], tot;
void init(int n)
{
	fill(head, head + n + 1, -1);
	tot = 1;
}
void add(int a, int b, ll c)
{
	e[tot] = edge{ b,c,head[a] };
	head[a] = tot++;
}
int du[MAXN];
ll ans[MAXN];
int main()
{
	int n, m;
	sc("%d%d", &n, &m);
	init(n);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		ll c;
		sc("%d%d%lld", &a, &b, &c);
		add(a, b, c);
		du[b]++;
	}
	queue<int>q;
	for (int i = 1; i <= n; i++)
	{
		if (du[i] == 0)
			q.push(i);
	}
	ans[1] = 1;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int i = head[t]; i + 1; i = e[i].nex)
		{
			int v = e[i].to;
			ans[v] = (ans[v] + ans[t]) % mod;
			du[v]--;
			if (du[v] == 0)
				q.push(v);
		}
	}
	pr("%lld\n", ans[n] % mod);
}