指定长度路径数
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description 题目给出一个有n个节点的有向图，求该有向图中长度为k的路径条数。方便起见，节点编号为1,2,…,n，用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500.
例如包含两个节点的有向图，图中有两条边1 → 2 ,2 → 1 。
长度为1的路径有两条：1 → 2 和 2 →1 ；
长度为2的路径有两条：1 → 2 → 1和2 → 1 → 2 ；
偷偷告诉你也无妨，其实这个图无论k取值多少 ( k > 0 )，长度为k的路径都是2条。
Input 多组输入，每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30.
Output 输出一个整数，即为图中长度为k的路径的条数。
Sample Input 3 0 1 0 0 0 1 0 0 0 2 Sample Output 1
代码语言：javascript复制#include<stdio.h>
int a[520][520],b[520][520],c[520][520];//b是中间商，c是最终结果
int main()
{
int n;
int i,t,q,j;
while(~scanf("%d",&n))
{
for(i=0;i<=n-1;i )
for(t=0;t<=n-1;t )
{
scanf("%d",&a[i][t]);
b[i][t]=a[i][t];
c[i][t]=b[i][t];
}
int k;
scanf("%d",&k);
for(j=1;j<k;j )
{
//c=b*a
//b=c
for(i=0;i<=n-1;i )
for(t=0;t<=n-1;t )
{
c[i][t]=0;//每次都要初始化一次，让c只存结果，而不是结果的累加
for(q=0;q<=n-1;q )
{
c[i][t] =b[i][q]*a[q][t];
}
}
for(i=0;i<=n-1;i )
for(t=0;t<=n-1;t )
b[i][t]=c[i][t];
}
int s=0;
for(i=0;i<=n-1;i )
for(t=0;t<=n-1;t )
{
if(k<=1)s =b[i][t];
else s =c[i][t];
}
printf("%dn",s);
}
}
