简单图论：迷路-Toy模板网

这篇具有很好参考价值的文章主要介绍了简单图论：迷路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

迷路

题目描述

windy 在有向图中迷路了。

该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$ 。

现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？

答案对 $2009$ 取模。

注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

输入格式

第一行包含两个整数，分别代表 $n$ 和 $t$ 。

第 $2$ 到第 $(n + 1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符，若为 $0$ ，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$ 。

输出格式

输出一行一个整数代表答案对 $2009$ 取模的结果。

样例 #1

样例输入 #1

2 2
11
00

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

样例输入输出 1 解释

路径为 $\to 1 \to 2$ 。

数据规模与约定

对于 $30\%$ 的数据，保证 $\leq 5$ ， $\leq 30$ 。
对于 $100\%$ 的数据，保证 $\leq n \leq 10$ ， $\leq t \leq 10^9$ 。

解题思路

矩阵快速幂

由于题目中给出的 $t$ 范围很大，故此题不能直接使用图论或者动态规划的方法。
简易版本
假设先不考虑每条路径间的具体距离，只用 0，1 表示两个结点间边连接的情况，可以使用邻接矩阵表示输入的有向图，该邻接矩阵记为 $A$ 。

在矩阵中，一个存i到j路径数的矩阵自乘k次，a[i][j]表示从i到j走k步的路径数。
证明： $c [i] [j] + = a [i] [k] * b [k] [j]$ ，
枚举一个中间点，用乘法原理，i到j两步的路径数等于i到k一步的路径数乘k到j一步的路径，然后再对于不同的中间点用加法原理，每次都枚举了i能到的所有点，以及能到j的所有点。
即矩阵 $A^x[i][j]$ 的值为结点 $i$ 走到结点 $j$ 经过 $x$ 步的情况数。因此，如果只有 0，1 表示两个结点间边连接的情况，那我们就可以通过矩阵快速幂的方式求解。
实际——带权重
因为边权可能为1～9,如果直接存进矩阵的话，存边权显然是不可取的，表示有边权数条路径，存1好像成了一步就能到。
1、输入的结点不超过 10 个
2、两两结点之间的距离也不超过 10
拆解节点——把一个结点拆成 10 份，通过结点内部分结点的连接来模拟不同结点间的距离。这样，拆完结点后邻接矩阵的大小也不会超过 $100\times100$ 。

通过拆点操作将距离不为 1 的结点一一转化为只有 0，1 的邻接矩阵后，就可以使用矩阵快速幂求解了。

Code

Python3

由于 Python 语言本身执行效率较低，因此该代码直接提交会超时，完成最大的测试用例时间在 11s 左右。文章来源地址https://www.toymoban.com/news/detail-518275.html

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
MOD=2009
n,t=map(int,input().split())

spn=n*10
class matrix:
    def __init__(self):
        self.m=[[0]*205 for i in range(205)]
    def __mul__(self,other):
        res=matrix()
        for i in range(1,spn+1):
            for j in range(1,spn+1):
                for k in range(1,spn+1):
                    res.m[i][j]=(res.m[i][j]+self.m[i][k]*other.m[k][j])%MOD
        return res

def check(i:int,j:int):
    return (i-1)*10+j

def power(x:matrix,n:int):
    ans=matrix()
    for i in range(1,spn+1):
        ans.m[i][i]=1
    while n:
        if n&1:
            ans=ans*x
        x=x*x
        n>>=1
    return ans


A=matrix()
for i in range(1,n+1):
    for j in range(1,10):
        A.m[check(i,j)][check(i,j+1)]=1
    dis=[0]+[int(j) for j in input()]
    for j in range(1,n+1):
        if dis[j]:
            A.m[check(i,dis[j])][check(j,1)]=1
    
res=power(A,t)
print(res.m[1][10*n-9])