短路专题
poj 1511 Invitation Cards(spfa最短路)
题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)
poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
poj 1502 MPI Maelstrom（单源最短路dijkstra）
题目真是长得头疼，好多生词，给跪。 没啥好说的，英语大水逼。 借助字典尝试翻译了一下，水逼直译求不喷 Description： BIT他们的超级计算机最近交货了。（定语秀了一堆词汇那就省略吧再见） Valentine McKee的研究顾问Jack Swigert，要她来测试一下这个系统。 Valentine告诉Swigert：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问
poj 3159 （spfa差分约束最短路） poj 1201
poj 3159: 题意： 每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。 解析： 差分约束。 这个博客讲差分约束讲的比较好： http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码： #include <iostream>#include <cstdio>#i
hdu 3790 (单源最短路dijkstra）
题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
poj 3255 次短路（第k短路） A* + spfa 或 dijkstra
题意： 给一张无向图，求从1到n的次短路。 解析： A* + spfa 或者 dijkstra。 详解见上一题：http://blog.csdn.net/u013508213/article/details/46400189 本题，spfa中，stack超时，queue的效率最高，priority_queue次之。 代码： #include <iostream>#i
poj 2449 第k短路 A* + spfa
poj 2449： 题意： 给一张有向图，求第k短路。 解析： A* + spfa。 一下转自：http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式：f(x)=g(x)+h(x);对h(x)进行设计，根据定义h(x)为当前的x点到目标点t所需要的实际距
poj 3259 最短路负环
John的农场里N块地，M条路连接两块地，W个虫洞，虫洞是一条单向路，会在你离开之前把你传送到目的地，就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。简化下，就是看图中有没有负权环。有的话就是可以，没有的话就是不可以了。 import java.io.BufferedReader;import java.io.InputStream;
POJ1724最短路
n个点，拥有总的价值money m条边（u，v,len ,cost），长度len，代价cost 求不超过money的代价条件下最短路。 public class Main {public static void main(String[] args) {new Task().solve();}}class Task {InputReader in = new InputReader
【AcWing】851. 求最短路
spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新，但是每一次迭代的话我不一定每条边都会更新，SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话，那么一定是dist[a]变小了，只有a变小了，a的后继(b)才会变小。 用宽搜来做优化，用一个队列，队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁，我再拿
【Codeforces】449B Jzzhu and Cities 最短路
传送门：【Codeforces】449B Jzzhu and Cities 题目大意：一个n个节点的无向图，节点编号1~n（其中1为起点），其中有m条普通普通，还有k条从起点出发的特殊边，问最多去掉多少的特殊边使得从起点到其他所有点的最短路径的距离不变。 题目分析：这题的意图很明显啊，就是要我们去求最短路啊。那么怎么求会比较好呢？其实我们可以很容易的发现如果从起点通过边权为c的特殊
【UVALive】3661 Animal Run 平面图最小割 最短路
传送门：【UVALive】3661 Animal Run 题目大意：给你一个n*m个点的网格图，其中动物园在左上角，动物们的目的地在右下角，现在你需要派出一些工作人员拦截某些边使得没有一只动物能到达右下角，已知每个单元网格中存在左上角到右下角的对角线，网格中的边以及对角线都是双向的，每条道路有个权值，表示拦截这条边所需要的工作人员数。你的任务是派尽量少的工作人员使得达到目的。 题目分析
【HDU】2807 The Shortest Path 最短路
传送门：【HDU】2807 The Shortest Path 题目分析：题目很简单，矩阵计算出两个城市的连通性，建边，然后每次询问求最短路回答（或者floyd预处理）。 当然暴力的代价是惨痛的，用堆优化+dij+输入优化最多800ms。 然后很好奇前面的是怎么跑的这么快的，看了别人写的题解才发现，原来他们是用了hash的方法将二维化为一维了，虽然可能会错误，但在出题人不是故意去卡的情
【HDU】3986 Harry Potter and the Final Battle 最短路
传送门：【HDU】3986 Harry Potter and the Final Battle 题目分析：先求一次最短路，同时记录在最短路上的顶点以及以该顶点为弧尾的最短路上的边。然后枚举删除每一条边，分别求一次最短路，其中最大的即答案。当然不可达输出-1。 测试发现堆优化的dij不如slf优化的spfa。。可能图太稀疏了吧。。。反正我觉得我写的挺搓的了。。。 代码如下：
【HDU】1595 find the longest of the shortest 枚举+最短路
传送门：【HDU】1595 find the longest of the shortest 题目分析：首先求出一条最短路，记录下最短路上用到的边，枚举删除每一条边，求一次最短路，求完后恢复删除的边。重复这一过程直到枚举完所有的边为止。所有删除边后求得的最短路里最长的那条就是答案。 代码如下： #include <cstdio>#include <cstring>
【HDU】4871 Shortest-path tree 最短路+点分治
传送门：【HDU】4871 Shortest-path tree 题目分析： 学了点分治后来看这道题，简直就是水题。。。 但是我竟然花了将近一个晚上才写出来。。。就因为一个地方写漏了T U T。。 首先根据题意求一棵树，最短路一下，然后最小字典序就按照编号顺序遍历邻接表给节点标记。 剩下的就是树分治的事了。 在以重心X为根的子树中，按照X的子节点v的子树中最长路径包含节点数升序遍
【HDU】5025 Saving Tang Monk 状压最短路
传送门：【HDU】5025 Saving Tang Monk 题目分析：这题一开始想都没想就敲了优先队列+dij。。然后TLE了。。。 后来发现是一个稀疏图。。换成spfa就过了。。 这是一个四维最短路，x轴，y轴，拿到第几个钥匙，打怪的状态（状压），然后就是很简单的状压最短路了。 要注意到钥匙不用状压，因为拿到钥匙是有顺序的。 代码如下： #include <c
【Live Archive】6395 SurelyYouCongest【最短路+最大流】
传送门：【Live Archive】6395 SurelyYouCongest 题目分析：我们只要从点1开始做一次最短路预处理，然后对于给定的源点们，对于最短路图构成一个层次图，然后由于每一层都是互不影响的，所以我们对每一层暴力跑网络流就好了。 my code: my~~code: #include <stdio.h>#include <string.h>#include <set>
【Tsinsen】1228 飞飞侠【并查集优化最短路】
题目链接：A1228. 飞飞侠 #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 155 ;const LL INF = 1e18 ;struct Node {LL dis ;in
【POJ】2449 Remmarguts' Date【k短路】
题目链接：Remmarguts’ Date k短路模板题，用这题验证了我可持久化左偏树的正确性。 #include <stdio.h>#include <vector>#include <queue>#include <algorithm>using namespace std ;typedef long long LL ;typedef pair < int , int > pii
HDU1874_畅通工程续（Dijkstra最短路）
畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 23022 Accepted Submission(s): 8085 Problem Description 某省自从实行了很多年的畅通工程计划后，终
POJ训练计划1062_昂贵的聘礼(最短路)
昂贵的聘礼 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 35560 Accepted: 10171 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说
算法训练营|图论第10天 Bellman_ford:优化算法，判断负权算法，单源有限最短路
题目：Bellman_ford:优化算法 题目链接： 94. 城市间货物运输 I (kamacoder.com) 代码： #include<bits/stdc++.h>using namespace std;struct Edge {int to;int val;Edge(int t, int w) :to(t), val(w) {}};int main() {int n, m;c
最短路算法详解（Dijkstra 算法，Bellman-Ford 算法，Floyd-Warshall 算法）
文章目录 一、Dijkstra 算法二、Bellman-Ford 算法三、Floyd-Warshall 算法 由于文章篇幅有限，下面都只给出算法对应的部分代码，需要全部代码调试参考的请点击： 图的源码 最短路径问题：从在带权图的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。涉及到三个算法： 单源最短路径：Dijkstra 算法（迪杰斯