P1849 图 - 题解

登录注册上岸

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

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

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

2026年3月5日 16:45

图本来代码是83%ac，问了ai应该是没有IO提速和直接引用题解：

P1849

回复 0 | 赞 12 | 浏览 320

#include<bits/stdc++.h> using namespace std; const int N = 2005; const int M = 805; int value[N]; // 每个节点的价值 vector<pair<int,int>> g[N]; // 邻接表：g[u] 存 (v, w) 表示 u -> v 代价 w bool visited[N][M]; // 记忆化标记：状态 (u, c...

2021年3月9日 15:09

图-深度优先遍历

P1849

回复 1 | 赞 36 | 浏览 8.9k

思路都写在注释里了，可以先看注释，再看代码 #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 | 赞 3 | 浏览 4.2k

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

2023年3月15日 14:46

解决Time Limit Exceeded问题

P1849

回复 1 | 赞 3 | 浏览 3.4k

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

题目图

题解数量4

发布题解在线答疑

热门题解

1 图-深度优先遍历

2 图本来代码是83%ac，问了ai应该是没有IO提速和直接引用题解：

3 解决Time Limit Exceeded问题

4 解题思路：记忆化