最短路

算法引入： *求一个图G中的最小环路的朴素算法为:每次找到一条边,删除了求这两点之间的最短路径; *若能求出,则这条最短路径与原来的边构成一个环,不过时间复杂度略高; *算法思想; *Floyd算法是按照顶点的编号增加的顺序更新最短路径的; *如果存在最小环,则会在这个环中的点编号最大的那个点u更新最短路径之前发现这个环; *即当点u被拿来更新i到j的最短路...

题意：~ 思路：先处理出乘坐出租车能到达的点，建图跑最短路即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100010; const LL INF = 1e18 + 7; const int lowINF...

题目链接：点我~~ 题意：1000个点10000条边的无向图，敌人从n走一条最短路到1，在第i条路设置障碍的代价是wi，求最少的代价使得敌人至少会遇到一次障碍。 思路：先确定最短路，然后在最短路径上跑一个网络流，即可求出最小割。 #include <bits/stdc++.h> using namespace std; typedef lon...

题目链接：点我~~ 题意：在N个点，M条带权边的图上，查询从点S到点E的最短路径，并且有一次机会可以把一条边的权值变成原来的二分之一。 思路：利用分层图的思想建图， u->v需要建立，addedge(u+n,v+n)，addedge(u,v+n,w/2)，表示分两层，当从上层到下层，即使用了题中所给的条件。 #include <bits/stdc...

题意：n个点，m条边，构建有权无向图。求出删去最少条边数没有最短路，以及删出最多条边，使最短路的长度不变。 思路：先处理出最短路，然后使用结果的dis数组，若dis[v]-dis[u] = w(u,v)，则该路就是最短路经中的一条边。建出最短路径之后跑最大流，流量是有多少边权相同的重边，跑出来就是最小割，也就是阻断所有最短路的最小花费。最后再跑最短路，边权为...

将每个字符串的前后四位取出，如果A串的后面四位跟B串的前面四位相等，说明A可以通往B，然后以此建图，直接跑最短路就可以了 #include<iostream> #include<cstdio> #include<string> #include<string.h> #include<algorithm&g...