dp松弛问题(循环特性) 题意： 分析： dp松弛问题。这是我的总结。所谓的最短路，不过是dp只不过该dp无法借由循环和记忆化搜索实现(因为有环使其左右横跳)详细见我的另一篇题解，正好是题单中的下一题：https://blog.nowcoder.net/n/8316b13c345d49b08b2
展开全文
思路 求能从 1 号点到达 n 号点 并且 满足相关条件的最短路条件：穿过的被***城镇 不能超过 K 个 解法：最短路 ＋ dp dist[i][j]：从起点开始 穿过了j个被***的城市 到达i点的 最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新 所
展开全文
题目描述 Island 发生了一场***！现在 Rinne 要和 Setsuna 立马到地上世界去。众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵***，虽然主角可以逆天改命强闯，
展开全文
【请修复它】
我发现这题的ac代码使用bfs和dfs的都有问题
比如说测试数据如果是
5 5 1
0
1
0
1
0
1 2 1
2 4 1
4 5 10
1 3 10
3 4 10
ac的bfs代码和dfs都会输出-1，实际上你人工模拟一下应该是30
这些代码产生这个错误的原因是因为没有使用二维数
展开全文
//迪杰斯特拉算法配合上动态规划
//动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路
//一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。
#include <bits/stdc++.h>
using&
展开全文
没有用dp的一种解法
本题的测试数据真的有点水，以至于我在忽略了一些重要细节的情况下都AC了
如果你也通过了这题但感觉有哪里不对劲，可以来看看这个题解
我不能保证我修改过的题解一定能严格通过题意，建议还是学习一下大佬用dp的题解
说说做法
这题除了多了一个k之外就是最短路的板题
处理k：定义一
展开全文
最短路，注意理解题意；只要一个戒备点次数增加，所有的戒备点次数都增加； #include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18;
const int maxn=6000;
展开全文
题目意思 #pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
