大连海事大学xcx

最短路径

CodeForces(33) kmp(6) 一通乱写(13) 二分思想(4) 代码待改(4) 动态规划(60) 区间问题(2) 字符串处理(14) 实用程序(4) 小结论速证(2) 尺取技巧(6) 思维(8) 拓扑排序(4) 排序处理(5) 搜索(45) 数学(4) 数据结构(38) 数论(15) 暴力(2) 最小生成树(8) 未归档(33) 树(1) 模拟(10) 比赛后总得写点什么(7) 社团故事(2) 简单作业(19) 算法讲堂附加代码(1) 类模板(2) 线段树(2) 网络流(10) 英语阅读理解(12) 读书笔记(4) 贪心(14) 题解集合(3) 魔板(2)

/ 注册

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

POJ - 2253 Frogger解题报告

Dijkstra算法变形题目大意：一个直角坐标系，给出所有点的坐标，以及两个确定的点，问从一个点到另一个点使经过的边中最长的边尽可能短，最短为多少。点数n<1000,测试实例数200 . 一开始的错误思路： 1假设A为起点B为终点 2算出所有的点之间的距离O（n^2） 3把各个点和A点之...

2017-02-04

0 393

POJ - 1062 昂贵的聘礼解题报告

昂贵的聘礼 POJ - 1062 终于有一到中文的题了，好激动。哈哈哈。。。题目大意： ez要去搞对象，酋长的女儿。那不就是寒冰嘛。。。。大概就是个Bellford-Ford算法。开始理解的很乱，然后根据测试实例画了个图。思路：比如要是想要B需要100元，用A换就只需...

2017-02-03

0 375

POJ - 1062 昂贵的聘礼解题报告

昂贵的聘礼 POJ - 1062 终于有一到中文的题了，好激动。哈哈哈。。。题目大意： ez要去搞对象，酋长的女儿。那不就是寒冰嘛。。。。大概就是个Bellford-Ford算法。开始理解的很乱，然后根据测试实例画了个图。思路：比如要是想要B需要100元，用A换就只需...

2017-02-03

0 376

关于Bellman-Ford算法的理解

这篇博客写废了，以后改。2017.4.9 Bellman-Ford算法，对于一个有向图，可以分别求出图中所有点到一个确定点的最短距离。基本思想就是枚举每一个点，判断通过该边能否使得其起点到原点的距离变短。如：对于边3-2，它可以使3-1变成3-2-1，从而使其距离变短，此过程称为...

2017-02-03

0 382

关于Bellman-Ford算法的理解

这篇博客写废了，以后改。2017.4.9 Bellman-Ford算法，对于一个有向图，可以分别求出图中所有点到一个确定点的最短距离。基本思想就是枚举每一个点，判断通过该边能否使得其起点到原点的距离变短。如：对于边3-2，它可以使3-1变成3-2-1，从而使其距离变短，此过程称为...

2017-02-03

0 498

POJ - 1860 Currency Exchange解题报告

Bellman-Ford 算法描述： 1.创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0； 2.计算最短路径，执行 V - 1 次遍历；对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于...

2017-02-01

0 448

POJ - 1860 Currency Exchange解题报告

Bellman-Ford 算法描述： 1.创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0； 2.计算最短路径，执行 V - 1 次遍历；对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于...

2017-02-01

0 409