[TIOJ] 1557. 馬可波羅的奇想曲
題目連結:http://tioj.infor.org/problems/1557
邊DFS邊DP,只要知道起點到起點的走法是一種,然後每次都詢問他的來源走法有幾種,大概這樣吧
邊DFS邊DP,只要知道起點到起點的走法是一種,然後每次都詢問他的來源走法有幾種,大概這樣吧
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define N 10000
#define modBASE 1073741824
vector<int> graph[N + 10];
lld val[N + 10]={0};
bitset<N + 10>dped;
lld dp(int);
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
graph[b].PB(a);
}
int Start,End;
scanf("%d%d",&Start,&End);
val[Start]=1;
dped[Start]=1;
lld ans = dp(End);
printf("%lld",ans);
return 0;
}
lld dp(int w){
if(!dped[w]){
lld sum=0;
for(int i=0;i<graph[w].size();i++){
sum += dp(graph[w][i]);
sum %= modBASE;
}
val[w]=sum;
dped[w]=1;
}
return val[w];
}
留言
張貼留言