青烟绕指柔

最短路

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

小D的旅行

题目描述旅行是一件颇有趣的事情，但是在旅行前规划好路线也很重要。现在小D计划要去U国旅行。 U国有N个城市，M条道路，每条道路都连接着两个城市，并且经过这条道路需要一定的费用wi。现在小D想要从u城市到v城市，但是他的汽车需要在途中加一次油(途中包括u和v两个城市)。在每个城市加油都有不...

2019-12-27

0 523

邮递员送信

题目链接：落谷P1629 题目描述有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间...

2019-12-27

0 491

hdu-3499 分层图最短路入门

Flight Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 5058 Accepted Submission(s): 1146 Pro...

2019-12-27

0 435

P4568 [JLOI2011]飞行路线

再来一个简单的分层图练习：题目描述 Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市...

2019-12-27

0 649

南昌网络赛 - Fire-Fighting Hero

题目链接：Fire-Fighting Hero 大意：给出多个点，问这些点，到所有点的最短路当中的最大值是多少。和一个单独的点到所有点的最短路的最大值除C之后比较，输出最小的最大值。我们肯定不能以每一个点去跑最短路，我们分析可知，因为从每个点出发是一样的，所以我们可以单独建立一个点，指...

2019-12-27

0 425

小doge的快乐阳光跑

题目链接：小doge的快乐阳光跑我们可以想一下，如果我们最开始肯定是从两个人的起点的其中一个作为起点，而且我们每次肯定是走最短路到达下一个任务点。所以我们要预处理出所有任务点的最短路，然后每次跑的时候，我们可以想到，走最短路去做的任务有两个，到底是去哪一个任务点呢？于是我们可以想到dp，...

2019-12-27

0 500

[CQOI2015]网络吞吐量

题目描述路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法...

2019-12-27

0 611

POJ 3613 Cow Relays

题目大意：起点到终点经过边的数目为k的最短路值为多少。离散数学的定理： 01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路。但是每次floyd的复制度...

2019-12-27

0 666

HDU - 3313 Key Vertex(找关键点)

Key Vertex Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1651 Accepted Submission(s): 428 P...

2019-12-27

0 523

Codeforces - F. K-th Path

F. K-th Path time limit per test2.5 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a connected un...

2019-12-27

0 505