Charlesss

ACM_最短路

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

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

POJ Test for Job(DAG上拓扑排序)

题目链接：http://poj.org/problem?id=3249 题意是给了n个点，m条边(单向边)，然后每个点都有一个点权(存在负权)，问从入度为0的点开始到出度为0的点，最大的权值和为多少。题目中说了这是一个DAG图(有向无环图)，跑最长路的话会超时...

2019-01-27

0 674

ACM-ICPC 2018 沈阳赛区网络预赛 D. Made In Heaven(k短路)

题目链接：https://nanti.jisuanke.com/t/31445 题意是输入n和m表示n个点m条边，然后输入起始点和终止点和第k短路和一个限制条件T，然后输入m条边。问能不能在T时间内从起始点到达终止点。做法就是裸的k短路，当返回值为-1和时间大...

2018-11-02

0 727

POJ 2449 Remmarguts' Date(k短路模板)

题目链接：http://poj.org/problem?id=2449 题意是n个点，m条边，然后输入m条边，最后输入起始点和终止点和第k短路。是一个k短路的模板题(赤裸裸的)，呆码也可以存下来当模板用，主要是spfa+A*实现的。 AC代码： #in...

2018-11-02

0 487

HDU 6181 Two Paths(次短路+dijkstra)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6181 题意是有两个人比赛，第一个人一定会走最短路，问第二个人最短走多远(不能与最短路路径完全相同)。其实就是一个次短路问题，我用的dijkstra+链式前向星.....

2018-10-31

0 502

POJ 3259 Wormholes(spfa判负环)

题目链接：http://poj.org/problem?id=3259 题意是有n个点，m条边，k个虫洞(权值为负)，输入完m条无向边后输入k条有向边，问能不能找到一个点，从这个点出发，最后回到这个点的时候权值是负的(时光倒流)。首先这个可以用Floyd去跑一...

2018-10-25

0 492

HDU 1317 XYZZY(spfa跑正环)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1317 题意是最多有100个房间，从1-n，然后每个房间都有一个能量值(可正可负)，每到达一个房间就会获得这个房间的能量值，起点为1，刚开始会有100点能量值，问最后能不能到达n点且...

2018-10-24

0 428

HDU 3339 In Action(dijkstra+01背包)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3339 题意是有n个点m条边(点的编号是1-n)，起点为0，每个点都有一个权值k，每条边也都有一个权值d(点到点的距离)，现在起点有一个坦克要去摧毁任意个点，使得这些被摧毁的点的权值...

2018-10-17

0 498

POJ 1847 Tram(详细题意+dijkstra)

题目链接：http://poj.org/problem?id=1847 题意是输入n,a,b三个数，表示有n个点(1-n)，起点是a，终点是b，然后接下来有n行，每一行的第一个数m表示后面将会有m个数，输入结构是这样的，然后我再具体的解释一下。 3 2 1 ...

2018-10-15

0 510

HDU 2923 Einbahnstrasse(dijkstra)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2923 题意是输入n,c,r，表示有n个城市，c个坏了的车，r条路，然后输入一个地名表示当前所在地，然后输入c个地名表示坏了的车的所在地，然后输入r行，每行三个字符串，中间的字符串表...

2018-10-11

0 426

HDU3790 最短路径问题(dijkstra+思维)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3790 其实就是裸的dij，只不过加了一个数组用来存花费，而且需要注意的是因为要求最短路程的最少花费，所以需要在松弛的时候对花费进行更新操作，当时没有加这个wa了n发... AC...

2018-10-09

0 476