MZ test17# NOIP模拟题 # T4 第4题 路线统计(route.cpp/pas)[key:矩阵]
第4题 路线统计(route.cpp/pas)
【问题描述】
给出一个n个点有向图,求从s点到f点恰好经过时间t的路径总数。不能在某个点停留,可以重复的走各点。
【输入数据】
第一行包含一个整数n, 所有点是从0到n-1编号.
接下来n行,每行包含n个字符. 第i行第j个字符表示i到j需要的时间,字符只可能是’1’到’5’, 或者是’.’表示i不能到达j, 保证主对角线都是’.’。
接下来一行3个整数s, f, t。
【输出数据】
输出总方案数mod 502630的值。
【样例输入】route.in
3
.12
2.1
12.
0 2 5
【样例输出】route.out
8
【数据范围及提示】
对于20%的数据, 输入的字符不是’1’就是’.’;
对于100%的数据, 1 <= n <= 10; 1 <= s,f <= n; 1 <= t <= 10^9
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std