P1849 图 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2021年3月9日 15:09

图-深度优先遍历

P1849

回复 1 | 赞 15 | 浏览 8.5k

思路都写在注释里了，可以先看注释，再看代码 #include <bits/stdc++.h> #define maxn 2005 int v[maxn]; int mp[maxn][maxn]; int result; int n,m,q; int u,limit; void dfs(int beg,int limit,int value){ if(value>result) //这个result是个全局变量，每一条路径进来的时候，都会进...

2023年3月17日 17:38

解题思路：记忆化

P1849

回复 0 | 赞 2 | 浏览 3.9k

这个题的难点在于Q的次数，1e5次查询。所以我们需要在普通的dfs搜索的基础上加上记忆化操作，这样可以保证每个点的每个距离只会计算一次。时间复杂度是：O（N * c）等于 2000*800

2023年3月15日 14:46

解决Time Limit Exceeded问题

P1849

回复 1 | 赞 2 | 浏览 3.1k

这道题的输出有点奇怪，用正常的cout<<输出可能会报错。使用 void wr(int x) { if (x > 9) wr(x / 10); putchar(x % 10 + '0'); } wr(dp[][]);

题目图

题解数量3

发布题解在线答疑

热门题解

1 图-深度优先遍历

2 解决Time Limit Exceeded问题

3 解题思路：记忆化