本文主要是介绍【SCOI2009】迷路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Description
windy在有向图中迷路了。
该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图,你能告诉windy总共有多少种不同的路径吗?
注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。
Input
第一行包含两个整数,N T。
接下来有 N 行,每行一个长度为 N 的字符串。
第i行第j列为’0’表示从节点i到节点j没有边。
为’1’到’9’表示从节点i到节点j需要耗费的时间。
Output
输出一个整数,可能的路径数,这个数可能很大,只需输出这个数除以2009的余数。
Sample Input
2 2
11
00
Sample Output
1
Data Constraint
Hint
100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。
.
.
.
.
.
分析
.
.
.
.
.
.
程序:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int Max=150;
const int mo=2009;
int n,m,sum,t1;
int ans[Max][Max],a[Max][Max],t[Max][Max];void jzcf(int x[Max][Max],int y[Max][Max])
{memset(t,0,sizeof(t));for (int i=1;i<=n*9;i++)for (int j=1;j<=n*9;j++)for (int k=1;k<=n*9;k++)t[i][j]=(((long long)x[i][k]*y[k][j])%mo+t[i][j]+mo)%mo;for (int i=1;i<=n*9;i++)for (int j=1;j<=n*9;j++)x[i][j]=t[i][j];
}int main()
{scanf("%d%d",&n,&t1);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){char x;cin>>x;if (x=='0') continue;a[i][((x-'0')-1)*n+j]=1;}for (int j=2;j<=9;j++)a[(j-1)*n+i][(j-2)*n+i]=1;}for (int i=1;i<=n*9;i++)ans[i][i]=1;while (t1!=0){if (t1&1) jzcf(ans,a);jzcf(a,a);t1>>=1;}cout<<ans[1][n]%mo;return 0;
}
这篇关于【SCOI2009】迷路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!