bzoj1297

题意

给定一个\(n\)个点的有向图,给定邻接矩阵,每条边的距离都是\(1-9\),求从1号点走到\(n\)号点且距离恰好为\(T\)的方案数量%\(2009\). \(n<=10,T<=10^9\)

做法

将每个点拆成\(1-9\),\((i,j)\)连向\((i,j+1)\)

若存在边\((u,v,w)\),则\((u,w)\)连向\((v,1)\)

然后跑矩阵快速幂

原文地址:https://www.cnblogs.com/Grice/p/12579455.html

时间: 03-26

bzoj1297的相关文章

BZOJ1297 [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 包

Evensgn的OI学习笔记(一)——动态规划及其优化

Author : Evensgn Date : 2014-12-08 蒟蒻也要写笔记啦~ (1)矩阵乘法优化DP 矩阵乘法: 一个 a*b 的矩阵 M1 与一个 b*c 的矩阵 M2 相乘,得到一个 a*c 的矩阵 M3. M3[i][j] = sigma(M1[i][k] * M2[k][j])      ( i <= a; j <= c; k <= b ) M3 的一个元素 M3[i][j] 是矩阵 M1 的第 i 行与 M2 的第 j 列的每一个对应元素乘积的和. 注意:矩阵 M1