大连海事大学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篇）

算法设计与分析：最短路径问题（哈密顿回路+最短路）小学期实践

最短路径问题一、题目要求：二、子问题（1）哈密顿回路 1.问题建模描述给定一个n个结点，m条有向边（边权为正）的图，求出一条路径满足如下条件：条件一：该路径可以从任意节点开始，不过起点和终点必须相同。条件二：该路径除了起点和终点，其他结点都必须经过，且只能经过一次。条件...

2019-07-09

0 1415

POJ - 3259 Wormholes解题报告（Bellman-Ford判断有向图中是否有负权环）

题目大意：一个有向图，给你n个点，m条双向路径，以及t条虫洞。每条路径描述在两个点ab之间移动需要时间v。每条虫洞描述从a到b需要时间-v（类似于时空穿越）。现在就问你，一个人能否从某个点开始，通过若干次虫洞和路径，在他出发之前的每个时刻回到出发点。注意：两个点之间有可能有多条路径！分析： ...

2017-04-21

0 408

POJ - 3259 Wormholes解题报告（Bellman-Ford判断有向图中是否有负权环）

题目大意：一个有向图，给你n个点，m条双向路径，以及t条虫洞。每条路径描述在两个点ab之间移动需要时间v。每条虫洞描述从a到b需要时间-v（类似于时空穿越）。现在就问你，一个人能否从某个点开始，通过若干次虫洞和路径，在他出发之前的每个时刻回到出发点。注意：两个点之间有可能有多条路径！分析： ...

2017-04-21

0 372

POJ - 3268 Silver Cow Party解题报告（dijkstra分别求单源起点和单源终点的最短路）

题目大意：题目大意：给你一个有向图，n（1000）个点m（100,000）条路径让你求出各个点到x号点再回到他自己的最短路径的最大值。分析：用dijkstra算法可以分别求出各个点到x号点的最短路和x到各个点的最短路。注意要是用-1来表示该路不通，那代码实现过程中一定要多考虑好多情况...

2017-04-21

0 537

POJ - 3268 Silver Cow Party解题报告（dijkstra分别求单源起点和单源终点的最短路）

题目大意：题目大意：给你一个有向图，n（1000）个点m（100,000）条路径让你求出各个点到x号点再回到他自己的最短路径的最大值。分析：用dijkstra算法可以分别求出各个点到x号点的最短路和x到各个点的最短路。注意要是用-1来表示该路不通，那代码实现过程中一定要多考虑好多情况...

2017-04-21

0 305

POJ - 2240 Arbitrage解题报告

题目大意：一个图，从一个点到另个点，权值会乘一个数，问是否存在正权环。然后发现一个问题，用Bellman-ford的时候，判断是否存在负权回路只需要枚举一次所有的边，看是否还能松弛就可以了！ #include #include #include #include #define N...

acm 最短路算法

2017-02-04

0 511

POJ - 2240 Arbitrage解题报告

题目大意：一个图，从一个点到另个点，权值会乘一个数，问是否存在正权环。然后发现一个问题，用Bellman-ford的时候，判断是否存在负权回路只需要枚举一次所有的边，看是否还能松弛就可以了！ #include #include #include #include #define N...

2017-02-04

0 462

POJ - 1125 Stockbroker Grapevine解题报告

题目大意：散布谣言！给一个图，正权有向。问从哪个点开始到各个点的距离中最大的距离最短，是多少。 floyd算法 #include #include #include #include #define N 150 #define inf 0x3f3f3f using namespac...

acm floyd

2017-02-04

0 464

POJ - 1125 Stockbroker Grapevine解题报告

题目大意：散布谣言！给一个图，正权有向。问从哪个点开始到各个点的距离中最大的距离最短，是多少。 floyd算法 #include #include #include #include #define N 150 #define inf 0x3f3f3f using namespac...

2017-02-04

0 446

POJ - 2253 Frogger解题报告

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

2017-02-04

0 558