梨小畅

分类

题解(57)

/ 注册

全部文章（共7篇）

题解 | #追债之旅#

有边数限制的最短路 —— bellman_ford 模板题时间复杂度 O（nm） #include <bits/stdc++.h> using namespace std; const int N = 1010, M = 20010; struct node{ int a...

最短路

2021-07-14

2 554

题解 | #旅行#

思路枚举中转点，当中转点为 i 时对应得到：res_i = f[i][0] + f[i][1]那么最终的答案 res = max(-1，res_1，res_2，res_3，...... ，res_n)f[i][0]：点 i 可到达的最远点(记其为x) 与点 i 之间的距离f[i][1]：点 i ...

最短路小根堆预处理

2021-07-14

1 416

题解 | #迷宫2#

思路题意：求让蜥蜴没办法达到终点所必须花费的最小总代价我们通过把特殊的走道转化为墙壁（转换代价为g[i][j] ），来使蜥蜴最终无法到达终点 g[i][j]取不同值的意义：-1代表墙壁，0代表走道，而1到10^9之间的正整数代表特殊的走道。因为 g[i][j] = -1 代表已经是墙壁，故转...

最短路思维

2021-07-11

7 677

题解 | #Rinne Loves Dynamic Graph#

思路求从 1 到 n 的最短路，需注意的是图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会执行一次操作：x = 1/(1-x)，x 是边权，所有的 x 指所有边即边权会随着走过的边的数目的改变而改变所以该题不再仅仅是最短路问题，而是变成了最短路 + dp 问题...

最短路 dp 思维

2021-07-10

1 362

题解 | #小雨坐地铁#

根本不需要分层图，其实是dijkstra模板题思路让我们求从 s 到 t 的最短路关键点在于建边有手就行很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h> using namespace std; const int N = 1e3...

最短路

2021-07-09

6 499

题解 | #[NOIP2001]Car的旅行路线#

题意求从城市 A 到城市 B 的最少花费：最短路已知一个城市有四个机场，不妨令 A 城市中的四个机场为 a1 , a2 , a3 , a4 ，B 城市的为 b1 , b2 , b3 , b4 又因为各个机场彼此互通，所以本质是求: min ( d[a1][b1], d[a1][...

最短路

2021-07-08

1 638

题解 | #[NOIP2009]最优贸易#

题意在从 1号点到 n号点的路径中，选择两个城市 A 和 B，必须先选 A 再选 B，问能赚取的差价最大是多少A：买入水晶球B：卖出水晶球 ps：1 号点到 n 号点的路径可能不止一条 . 思路不妨遍历 n 个点，对于每个点求出 res_i = w2[i] - w1[i]w1[i]：买入...

预处理 dp 最短路

2021-07-08

2 431