子希

图论最短路

ACM动态规划(4) ACM花里胡哨(1) c++(4) Dijkstra(5) javafx开发(1) java学习(1) oj几何(1) oj贪心(7) oj递归(5) stl练习题(6) 动态规划(2) 单调栈(4) 图论最小生成树(6) 图论-网络流(1) 图论（杂）(5) 字典树(2) 字符串(8) 并查集(14) 思维题(23) 数据结构实现(2) 数据结构实验(2) 数论(1) 暴力(1) 暴力搜索(26) 有趣的数学题(1) 未归档(2) 树状数组(6) 模拟(3) 每日一题(1) 离散数学实验(5) 算法设计与分析题库(15) 线段树(10) 网络比赛(6) 题解(43)

/ 注册

全部文章 / 图论最短路（共8篇）

Calling Circles UVA - 247(floyd)

题目大意：a和b打电话，b和c打电话可以构成一个电话圈，a和b打电话，b不和a打电话这样不算构成电话圈（也就是说这是一个有向图，因为这个wa一次），然后要你求可以构成圈的成员。思路：先对输入的字符串转化为数字（难点），然后求传递闭包，最后遍历图。技巧：将字符串存储在who数组里面，字符对应数子用m...

2020-05-21

0 604

Audiophobia UVA - 10048(floyd)

这题比较简单应该算是裸题了，只需要在求i到j最短路的时候再求一下i到j的最大噪音就可以了，之前做过一道这样的题，一发ac了。(感觉自己的代码越来越精湛了hah，（自恋一波代码： #include<bits/stdc++.h> using namespace std; int n,m,...

2020-05-21

0 739

最短路习题集（dijkstra+堆优化 folyd spfa bellman-ford+fifo）

Til the Cows Come Home Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 92816 Accepted: 30207 Description Bessie is out in the field and ...

2020-05-21

0 516

1074 - Extended Traffic(spfa+判负环)

题目大意：给你n个顶点，和m条边，边权计算（终点-起点）的立方，然后要你求最短路，如果不存在这条路或者这条路权值<3，输出？。思路：因为（终点-起点）的立方有可能会出现负数因此我们不但要找最短路还需要判负环，因为有负数dijkstra就用不了了，这里用spfa找负环，用dfs把负环都染色。 ...

2020-05-21

0 584

Layout poj3169（差分约束+bellman-ford）

Layout Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 17567 Accepted: 8449 Description Like everyone else, cows like to stand close to ...

2020-05-21

0 509

hdu4725 The Shortest Path in Nya Graph（dijkstra+建图）

The Shortest Path in Nya Graph Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 16403 Accepted S...

2020-05-21

0 653

Candies poj3159（差分约束+dijkstra）

Candies Time Limit: 1500MS Memory Limit: 131072K Total Submissions: 42227 Accepted: 11859 Description During the kindergarten days, flymouse was th...

2020-05-21

0 528

Subway poj2502 （dijkstra+建图）

Subway Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16322 Accepted: 5207 Description You have just moved from a quiet Waterloo neighb...

2020-05-21

0 525