青竹qingzhu

最短路

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / 最短路（共10篇）

POJ2253---Frogger最小最大边

题目链接题意给n个石头的坐标，要求从一个石头到另一个石头路径上石头之间的长度的最小最大距离。思路最短路的变形，dijkstra算法是有一个核心条件，d[v] > d[u] + cost[u][v]则替换，因为到v的距离有更小的，这里可以用d[v] > max(d[u], cost...

2020-07-13

0 512

POJ - 1797最大最小边

题目链接题意 n个点，m条边，求从1到n的路径上最大的最小边，（如，有1 2 3，1 3 4， 2 3 5这几条边，从1到3最大的最小边就是4）思路松弛操作替换为d[v] = min(d[u], dis[u][v])，因为要找最大的边，所以每次进行松弛的的时候是找最大的边。 #include...

2020-07-13

0 364

POJ - 1860判断正环

题目链接题意有n种类型的货币，m个城市可以兑换两种货币，一个人手上有v块s类型的钱，要求判断是否可以经过若干次兑换后这个人手上的s类型的钱增加了。思路对于每种货币，建立一个点，两种货币可以交换，则这两个点之间有一条边，经过若干次兑换后要回到s类型的钱，则一定存在环，而钱要增加，则需要存在正...

2020-07-13

0 508

poj3360-floyd传递闭包

题目链接题意 n头牛，给出m个a打败b的结果，求有多少头牛的排名可以被确定。思路能确定排名的牛，也就是能确定击败它的牛的数量加上能确定被它击败的数量等于n-1,就可以确定排名。只需要判断能否到达，直接用floyd算法： mp[i][j]|=(mp[i][k]&mp[k][j]); ...

2020-07-13

0 626

POJ - 1511 Invitation Cards 往返最短路之和正向反向存边

题目链接题意给P个点Q条边的图，求所有点到1这个点的往返最短路之和。思路正向和反向分别存边，跑两遍dijkstra就可以了。 #include <iostream> #include <cstdio> #include <queue> #include ...

2020-07-13

0 432

POJ - 3159 Candies最大差异

题目链接题意 n个人分糖果，有m个约束条件，a认为b不能比他多c个糖果，求1和n的最大糖果数量差。思路约束条件等价为num[a] + c >= num[b]。相当于从a到b有一条等于c的有向边，这样就转换为了最短路问题，直接用dijkstra求1到n的最短路即可。参考大佬博客由p[...

2020-07-13

0 513

POJ - 1062 有限制的最短路

题目链接题意 n个人每人有一个物品，每个物品可以直接买，也可以通过其他物品抵押加上少量的钱买，每个人有一个等级，经过若干次交换购买的人中的最大等级差不能超过m。求要得到第一件物品的最少花费是多少？思路如果没有等级约束就是一个最短路的模板题，根据a物品加w个金币换到b物品，可以建立一条有向边a-...

2020-07-13

0 483

最少需要转90度的弯几次——建图

传送门题意给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。思路拐弯才要花费，把一个点拆成四个点，上下左右，从上到下和从左到右建双向边，边权为...

2020-07-13

0 506

1e5个点n+100条边求任意两点之间的距离——最短路

传送门题意 n个点m条边，q次询问求任意两点之间的距离。（n<=1e5，m<=n+100，所有边权为1，保证图连通）。思路这个多出的100多条边就很怪，先考虑如果没有多出边，就只有n-1条边，图连通，那么可以建立最小生成树，用LCA来做，任取一点为根，len[i]为i点到根的距离，...

2020-07-13

0 634

Rinne Loves Graph——分层图

传送门题意 n个城镇，有一些城镇被派兵***，求从1到n通过***的城镇不超过k次的最短距离。解法将在某个城镇通过了多少次***的城镇设为一个状态。 d[i][j]：从1到i通过了j次***的城镇。（或者是分层图的做法，建图的时候定义n*k个点，对于加入的一条边，连接能到达的所有状态。）用...

2020-07-13

0 705