#P14965. [2026年重庆省队集训]游走

    ID: 14181 传统题 1000ms 64MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>动态规划图论数据结构树状数组CF2000最短路排序枚举背包DP

[2026年重庆省队集训]游走

题目描述

给定一张 nn 个点的简单无向图。

小 A 在图上游走。他从 11 号结点出发,每一步都可以沿着当前结点的某条出边移动,或者留在原地不动。

有 mm 个得分条件,每个条件形如 (x,y)(x,y),表示若小 A 经过 xx 步后恰好在结点 yy,就能得一分。

小 A 想知道,他在一次游走过程中最多得多少分?

输入格式

第一行二个正整数 n,mn,m。

接下来 nn 行,每行一个长度为 nn 的 01 串。第 ii 行第 jj 个字符表示 ii 号结点和 jj 号结点之间是否有边连接。

接下来 mm 行,每行两个正整数 x,yx,y,表示一个得分条件。

输出格式

输出一行,包含一个整数,表示一次游走过程的最多得分。

样例输入 #1

5 5
00100
00110
11001
01001
00110
3 2
1 2
5 3
2 5
4 5

样例输出 #1

3

数据范围

对于所有数据,保证 1≤n≤5001\le n\le 500,1≤m≤1051\le m\le 10^5,1≤x≤1091\le x\le 10^9,1≤y≤n1\le y\le n。保证给出的图是简单无向图。

测试点编号 n≤n\le m≤m\le x≤x\le
1∼31\sim 3 500500 10510^5 500500
4∼64\sim 6 10510^5
7∼107\sim 10 10910^9

提示

请注意本题特殊的空间限制。