本文主要是介绍题目:「一本通 6.5 练习 3」迷路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
原题来自:SCOI 2009
Windy 在有向图中迷路了。 该有向图有 N 个节点,Windy 从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图,你能告诉 Windy 总共有多少种不同的路径吗?
注意:Windy 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。
输入输出格式
输入格式:
第一行包含两个整数,N,T;
接下来有 N 行,每行一个长度为 N 的字符串。第 i 行第 j 列为 0
表示从节点 i 到节点 j 没有边,为 1
到 9
表示从节点 i 到节点 j 需要耗费的时间。
输出格式:
包含一个整数,可能的路径数,这个数可能很大,只需输出这个数除以 2009 的余数。
输入输出样例
输入样例#1:
2 2
11
00
输出样例#1:
1
#include<bits/stdc++.h>
using namespace std;int n,t;
const long long Mod=2009;struct node {int g[205][205];void clear(){memset(g,0,sizeof g);}
}A;node YunSuan(node x, node y) {node now;now.clear();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {now.g[i][j]=(now.g[i][j]+x.g[i][k] * y.g[k][j])%Mod;}}}return now;
}void g(node &o){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) o.g[i][j]=1;else o.g[i][j]=0;}}
}
node Power(node a,int b){node now;now.clear();g(now);while(b){if(b&1)now=YunSuan(now,a);a=YunSuan(a,a);b>>=1;}return now;
}int Cheak(int i,int j){return (i-1)*10+j;
}int main(){scanf("%d%d",&n,&t);int N=n;n*=10;for(int i=1;i<=N;i++){for(int j=1;j<10;j++){A.g[Cheak(i,j)][Cheak(i,j+1)]=1;}for(int j=1;j<=N;j++){int x;scanf("%1d",&x);if(x){A.g[Cheak(i,x)][Cheak(j,1)]=1;}}}A=Power(A,t);printf("%d\n",A.g[1][10*N-9]);
}
这篇关于题目:「一本通 6.5 练习 3」迷路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!