[TIOJ] 1589. 蚯蚓之入侵雅勒問題 Athena

題目連結:http://tioj.infor.org/problems/1589
很明顯的可以知道到一個點的方法數,就是到所有連到他的人的方法數加起來,所以我們可以用類似DP的方法記錄從起點到每個點的方法數,而DP順序就按照拓樸排序就好了XD
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
const int N = 250 + 5;

vector<int> G[N];
lld way[N];
int in[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int vv, ee, m; cin>>vv>>ee>>m;
	for(int i=0;i<ee;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		in[v]++;
	}
	int st, ed; cin>>st>>ed;
	way[st]=1;
	queue<int> qq;
	for(int i=0;i<vv;i++) if(in[i]==0)
		qq.push(i);
	while(!qq.empty()){
		int u = qq.front(); qq.pop();
		for(auto v: G[u]){
			way[v] = (way[v]+way[u])%m;
			in[v]--;
			if(in[v]==0) qq.push(v);
		}
	}
	cout<<way[ed]<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology