基础学习
链表
.netcore
python 笔记
opencv
前缀和
cocos2dx-lua
文件
Python办公自动化
xml
损失函数
日志收集
camera
游戏程序
skill
树莓派
网络管理
ACK
下载视频
三星刷机
最短路
2024/4/11 14:34:37
acwing 1076 迷宫问题(最短路模型)
题面 题解(最短路模型) 迷宫问题输出路径，因为每个点之间的距离都是1，所以用BFS搜索出来的结果就是最短的距离，我们新开一个数组，然后我们从终点开始最终搜索到起点，记录每个点的前一个点是从哪转移过来的，…
acwing 188 武士分度的牛(最短路模型)
题面 题解 从起点开始，步数为0，然后BFS能走到’日’的方向，更新距离即可 代码
#include<bits/stdc.h>using namespace std;
typedef pair<int, int> PII;
const int N 160;int n, m;
char g[N][N];
PII q[N * N];
int dist[N][…
POJ1502，MPI Maelstrom（最短路）
没看题，直接看输入输出，猜出了大概就是求1到其他点的最短路径，输出其中的最大者。 然而还是WA了很多次，错了很多奇奇怪怪的东西（不知为啥在POJ刷题经常会遇到这种情况。。。） 注意一下数据的输入与处理吧。…
[CF827F]Dirty Arkady's Kitchen
Description
给出一张n个点m条边的无向图，每条边有存在时间区间[li,ri]，一开始一只Akagi在1号点，每个时刻她都必须要从某个点走到另一个点，每一条边所花费的时间为1，求Akagi走到点n的最小时间。 n,m<5*1e5
Solut…
【NOIP2013提高组day2】华容道
Description
给出一张n*m的棋盘，有一些点上有障碍物，其他点上都是棋子。给出q次询问，每次询问给出一个空格，一个目标棋子，一个目标位置，每一步可以把一个棋子移进空格，求把目标棋子移动到目标位…
【NOIP2013模拟】DY引擎
Description
给出一张无向图，问从1到n的最短路。 你可以瞬移k次，每次从u瞬移到v的条件是：u到v中存在一条不经过收费站的距离<L的路径。当然，u或v可以是收费站。 收费站不会直接告诉你。而是给出p个提示，每个提示…
bzoj 4289: PA2012 Tax
Description 给出一个N个点M条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点1到点N的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权N<100000M<200000Input Output Sampl…
51nod 1649 齐头并进 （两次dijkstra求最短路）
传送门：51nod 1649 题目大意：
在有铁轨直接相连的城市之间可以跑火车，在没有铁轨直接相连的城市之间可以修公路跑汽车。在两者不同时到达同一个城市的前提下，问汽车和火车从城市 1 到城市 n 走最优路的最大值是多少。 思路&#…
CSP第十二次 行车路线【80分】
问题描述 小明和小芳出去乡村玩，小明负责开车，小芳来导航。 小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，…
hdu 6026 Deleting Edges 【最短路+计数】
题目大意:给你一个图，要把它删成一棵树，并且使得0这个结点从树上到达任意结点的距离和原图中的最短路径相等
分析：我们对于某一个点来说，只需要知道有多少条和到这个点最短路的路径，乘起来就可以 注意个数是一个乘积…
[bzoj4356][ceoi2014] wall
Description
题意太复杂了不想讲 给你一个n*m的网格图，有一些点是关键点，点（1，1）一定为关键点 每条边有边权 问用一个可以自交的环包住所有关键点的最小边权和 n,m<400
Solution
wxh修墙 可以发现对于每一个…
acwing 851 spfa求最短路（spfa算法）
题面 题解 spfa算法用于求单源最短路，适用于图中存在负权边，但是不能有负环，O(m),最坏的情况下是O(nm) ，也可以求解dijkstra spfa其实就是队列优化的bellman-ford算法，bellman-ford算法每次迭代都要更新dist[b]dist[a]…
acwing 853 有边数限制的最短路 （Bellman-Ford算法）
题面 题解 如果图中存在负权回路，则不一定有最短路（我们更新距离，每次经过回路值就会减少，无限循环就会变为负无穷） 备份数组：每次迭代前，都要将原来的dist数组备份，防止发生串联&am…
CodeForces - 938D Buy a Ticket（建立源点+单源最短路）
Musicians of a popular band “Flayer” have announced that they are going to “make their exit” with a world tour. Of course, they will visit Berland as well.
There are n cities in Berland. People can travel between cities using two-directional train rou…
石油大 2019年第二阶段我要变强个人训练赛第十八场 Problem F 路（最短路）
链接：http://icpc.upc.edu.cn/problem.php?cid1803&pid5
题意：n个点、m条边。可以将一条边的长度变为两倍，问最多可以比原来的最短路多多少。
思路：找出最短路的所有边，然后枚举修改，再跑最短路。说…
GDOI 2016 Day2 T1 SigemaGO
Description
给出一张n个点，m条边的有向图。若A->B有一条边，B->C有一条边，则可以使用L的时间直接从A到C。总共只可以走lim次这样的近路。求1到n的最短路。若无解，输出-1。 n<10000,m<50000,lim<5
Solution
加了…
【数学建模】图论模型
文章目录 图的基础理论及networkx简介图的基本概念图的表示及Networkx简介图的表示NetworkX简介 最短路算法及其Python实现固定起点到其余各点的最短路算法每对顶点间的最短路算法最短路应用 最小生成树算法及其networkx实现基本概念最小生成树算法最小生成树应用 匹配问题最大…
数据结构--最短路径 Dijkstra算法
数据结构–最短路径 Dijkstra算法 Dijkstra算法 计算 b e g i n 点到各个点的最短路 \color{red}计算\ begin\ 点到各个点的最短路 计算 begin 点到各个点的最短路 如果是无向图，可以先把无向图转化成有向图 我们需要2个数组 final[] （标记各顶点是否已…
数据结构--BFS求最短路
数据结构–BFS求最短路 BFS求⽆权图的单源最短路径
注：⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为1 以 2 为 b e g i n 位置 以2为begin位置 以2为begin位置 代码实现
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u…
7-15 周游世界分数 30（堆优化版dijkstra）
周游世界是件浪漫事，但规划旅行路线就不一定了…… 全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求…
【蓝桥杯集训15】求最短路存在负权边——spaf算法（2 / 4）
——SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称
单源最短路，且图中没有负环就可以用spfa
目录
spaf求最短路模板
852. spfa判断负环
341. 最优贸易 -
3305. 作物杂交 - spaf求最短路模板 只有当一个点的前驱结点更新了，该节点才会得到…
最短路问题——（最短路径）
一、只有五行的算法——Floyd-Warshall 下图中有4个城市8条公路，公路上的数字表示这条公路的长短。注意公路是单向的。我们需要求出任意两个城市之间的最短路程，即任意两点之间的最短路径。 首先，我们建立一个数据结构来存储图的信息…
单源最短路解决多源汇最短路问题，1127. 香甜的黄油
1127. 香甜的黄油 - AcWing题库
农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。
当然，他将付出额外的费用在奶牛上。
农夫John很狡…
【蓝桥杯集训11】BFS（4 / 4）
目录
844. 走迷宫 - BFS求最短路
1233. 全球变暖 - BFS
845. 八数码 - 最短路BFS 状态表示 一二维坐标转换
为什么BFS保证走的是最短路？
一二维坐标转换（nn矩阵）
1562.微博转发 - BFS按层遍历 有向图 844. 走迷宫 - BFS求最短路
活…
图论+博弈论上dp：CF536D
此题其实比较板，只是我没看出来
首先肯定要跑个最短路，然后发现可以离散化把值域缩小
然后 n n n 很小，直接暴力列个 n 2 n^2 n2 dp。
转移要注意的是必须从大往小dp。从小到大会产生后效性。
然后拿个双指针优化下转移就行。
// LUOG…
算法随笔：Floyd
Floyd算法是一种对所有点对最短路径算法、多源最短路径算法，以此计算能得到图中每一对节点之间的最短路径。Floyd不仅可以用来求多源最短路，也可以用于解决传递闭包问题。 算法思想：
Floyd求最短路径用的是“从小图到全图”的动态规划思想&a…
【第二十二课】最短路：bellman_ford / spfa算法 (acwing-851 / acwing-853 / c++代码)
目录
前言
acwing-853
bellman_ford算法的思想
代码如下
一些解释
acwing-851
spfa算法思想
代码如下
一些解释 前言
由于权重可以表示不同的度量，例如距离、时间、费用等，具体取决于问题的背景，因此会存在一些权值为负数的题目。…
来自看错题意的一份代码
由于之前看错题意了，花了很长的时间写了一份代码 大概就是先求最短路，再求次短路的暴力算法 算是复习了一下最短路和路径记录吧，并且希望下次看清楚题意再做题。
如果按照代码翻译一下，就是建立一个图，求两点之间的…
约会怎么走到目的地最近呢？一文讲清所有最短路算法问题
🚀🚀🚀🚀🚀订阅专栏👉 趣学算法(dog) 👈 带你学习算法原理 算法模板🚀🚀🚀🚀🚀
write in front 朋友们好啊，好久没写过…
UVA247 Calling Circles 解题报告
题目链接
https://vjudge.net/problem/UVA-247
题目大意
如果两个人相互打电话（直接或间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这4个人在同一个圈里…
数据结构--最短路径 Floyd算法
数据结构–最短路径 Floyd算法 F l o y d 算法：求出每⼀对顶点之间的最短路径 \color{red}Floyd算法：求出每⼀对顶点之间的最短路径 Floyd算法：求出每⼀对顶点之间的最短路径 使⽤动态规划思想，将问题的求解分为多个阶段 对于n个顶…
HDU-6714 最短路 2 （最短路Dijstra+Floyd理解）
链接：http://acm.hdu.edu.cn/showproblem.php?pid6714
题意：就是求任意两点最短路中松弛点中最小值的和。
思路：Floyd第一层循环其实就是枚举的松弛点。枚举起点，每次跑一遍Dijstra，求所有松弛点的最小值即可。
#i…
HDU2962Trucking两种解法
题目传送门：trucking 题目大意： 卡车要运输尽可能高的物资，但是也有安全限高，城市间的道路是双向的，每条道路都有一个权值和限高，要求出运输尽可能高的物资的时候的最短路。 解题思路： 思路一&a…
【GDOI2014模拟】旅行（水法）
Description
给出一张n个点，m条边的图，你可以选择一些边，使得1和n,2和n-1,3和n-2…k和n-k1联通。代价为这些边的边权和。 求最小代价。 n<10000，m<12000，k<4
Solution
这是一种神奇的方（shui…
bzoj 1266: [AHOI2006]上学路线route
Description 可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。 可可：“很可能我们在上学的路途上浪费了大量的时间&#x…
图论（二）之最短路问题
最短路
Dijkstra求最短路 文章目录 最短路Dijkstra求最短路栗题思想题目代码代码如下bellman-ford算法分析只能用bellman-ford来解决的题型题目完整代码 spfa求最短路spfa 算法思路明确一下松弛的概念。spfa算法文字说明：spfa 图解： 题目完整代码总结ti…
LeetCode 1334. 阈值距离内邻居最少的城市：多次运用单源最短路的迪杰斯特拉算法
【LetMeFly】1334.阈值距离内邻居最少的城市：多次运用单源最短路的迪杰斯特拉算法
力扣题目链接：https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/
有 n 个城市，按从 0 到 n-1…
Codeforces Round #829 (Div. 1) D.The Beach(最短路/流量为1的费用流)
题目
n*m(n*m<3e5)的网格图，由空地、石头和1*2的床组成，
Andrew想在网格图上找一个1*2的空地用来放床，他可以把别人的床进行如下挪动：
①花费p(1<p<1e9)的代价，以床的一个端点为轴不动，
将另一…
acwing 1100 抓住那头牛(最短路模型)
题面 题解 我们可以将坐标轴看成一个图，从起点n开始，可以到达n1,n-1,n*2的点，要求n到k的最短距离，那么我们可以设到达每个点的距离是1，然后用bfs进行搜索，搜索到k时，dist[k]就是n到k的最短距离 …
POJ2387，Til the Cows Come Home（Dijkstra算法）
最短路Dijkstra的模板题，不过需要注意的是，这道题的图是无向图。 用了两种方式过这道题，一种是基本的方式，一种是借助优先队列优化的。 第一种代码：（要用邻接矩阵）
#include<cstdio>
#in…
【NOIP2015模拟11.3】IOIOI卡片占卜
Description
就像你看到的题目一样，现在有A个I,接着B个O,再接着C个I,再接着D个O,再接着E个I，排成一排。你现在有N种操作，第i种操作吧从第li个字符到第ri个字符这个区间内的字符，I变成O，O变成I，时间为ri-li…
CodeChef - CLIQUED Bear and Clique Distances(建虚点+最短路)
CLIQUED: 小熊与团间距离 题目描述 小熊国里有 N 座城市，编号为 1 ∼ N。城市间由双向道路连通。 编号为 1 ∼ K 的城市都是古城，那里的市民们喜欢秩序与规律。这些城市两两由长度为 X 的 双向道路连接，共有 K(K − 1)/2 条这样的道路。 此外…
spfa算法_C++详解
spfa定义 SPFA算法的全称是：Shortest Path Faster Algorithm，该算法是西南交通大学段凡丁于1994年发表的,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，其中k为所有顶点进队的平均次数，可以证明k一般小于等于2，可以处理负边，但无法处理带负环的图（负环和…
第 119 场 LeetCode 双周赛题解
A 找到两个数组中的公共元素 模拟 class Solution {
public:vector<int> findIntersectionValues(vector<int> &nums1, vector<int> &nums2) {unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());vector<…
图论 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）
文章目录 前言Part 1：朴素Dijkstra算法一、Dijkstra求最短路 I1.问题描述输入格式输出格式数据范围输入样例：输出样例： 2.算法 Part 2：堆优化Dijkstra算法一、Dijkstra求最短路 II1.题目描述输入格式输出格式数据范围输入样例&…
LeetCode 1976.到达目的地的方案数：单源最短路的Dijkstra算法
【LetMeFly】1976.到达目的地的方案数：单源最短路的Dijkstra算法
力扣题目链接：https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/
你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ÿ…
KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）（A~D）
A - Arithmetic Progression
给你A,B,D，输出A，AD，A2*D，...到B为止，一个循环就可以解决。
#include <bits/stdc.h>
//#define int long long
#define per(i,j,k) for(int (i)(j);(i)<(k);(i))
#define rep(i…
“新华三杯”第十届成都信息工程大学ACM程序设计竞赛（同步赛）L. 怎么走啊(最短路+二分 分段函数)
题目
登录—专业IT笔试面试备考平台_牛客网 思路来源
衡阳师范学院ac代码、pj学弟
题解 大致可以证明，在w从1e5减小到1的过程中，
之前某条反向边没有用到，现在需要用到反向边，也就是正向边用到的变少了
这样的变化有sqrt个&a…
CCF 201712-4 行车路线
思路：用两个数组维护到达某个点的最小大路距离和最小小路距离，注意结果中间过程可能爆int, 不加long long 只有70分。
有一种特殊情况就是通过走两次大路，消除连续的小路值，这里就是用两个数组维护的原因。
#include <bits/std…
第3章：搜索与图论【AcWing】
文章目录 图的概念图的概念图的分类有向图和无向图 连通性连通块重边和自环稠密图和稀疏图参考资料 图的存储方式邻接表代码 邻接矩阵 DFS全排列问题题目描述思路回溯标记剪枝代码时间复杂度 [N 皇后问题](https://www.luogu.com.cn/problem/P1219)题目描述全排列思路 O ( n ! …
【洛谷】P1828 [USACO3.2] 香甜的黄油 Sweet Butter （最短路）
1：做这种题(思路)
第1步：观察先定位为最短路类型
第2步：观察数据范围！这很重要，小数据咱就可以进行伪暴力（毕竟解决最短路的板子也不少）
第3步：库库开始敲！ 2…
SDUT 3562 第七届山东省ACM省赛 Proxy （dijkstra最短路 + 反向边）
传送门：SDUT 3562题目大意：
一个有编号 0~n1 点的有向图。
1. 如果从 0 点到 n1 点的最短路径不存在则输出 -1。
2. 如果最短路存在则输出最短路上离 0 点最近的点。
3. 如果存在多条最短路，则输出 节点编号小的离 0 点最近的点。
4. 如果该点…
Leetcode 第 377 场周赛题解
Leetcode 第 377 场周赛题解 Leetcode 第 377 场周赛题解题目1：2974. 最小数字游戏思路代码复杂度分析 题目2：2975. 移除栅栏得到的正方形田地的最大面积思路代码复杂度分析 题目3：2976. 转换字符串的最小成本 I思路代码复杂度分析 题目4&…
单源最短路的建图方式 , 1129. 热浪，模板题
1129. 热浪 - AcWing题库
德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！
他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。
农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶…
[51nod1326]遥远的旅途
Description
一张有n个点，m条变的无向图，每条边有边权。 在0时刻有一个人在点1，每一次他走过一条边，消耗的时间为这条边的边权，而不能停留在原地。 现在他想知道是否存在一种方案使得他在T时刻刚好到达点n。 多组数…
【LeetCode:2304. 网格中的最小路径代价 | dijkstra(迪杰斯特拉)】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…