题意给出一个有向图，需要从 $1$ 走到 $N$ ，可以在一个城市买水晶球并在另一个城市卖掉，也可以不买，问最多能赚多少钱。其中 点数$n\le 100000$ ，边数$m\le 500000$ 。题解分层图最短路。对于原图，买卖操作各建一层图，边权为在起点买卖水晶球的花费（买为负卖为正）。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ，对于每...
题意给一个无向图，求严格次小最短路。其中点数 $N\le 5000$ ，边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较，将较小值给最短路，较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重，可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
题意求 从$1$ 到 $N$ 的一条路径，使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ，边数 $P\le 2000$，权值 $L_i\le 10^{6}$题解直接求肯定没有办法，所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分，每次检验就跑一次 $Dijkstra$ ，只是把边权变为 $>x$ 的边的条数，这样就可以得到$>x$ 的边最少...
卧槽竟然一遍就A了，可把身为蒟蒻的我nb坏了刚开始让我做这道题，我是拒绝的，然后看完题发现，这就是道裸的最短路，连边搞就是了。然后发现它只给三个点，看了题解才知道第四个点可以用向量点乘判断垂直来求，路燕我对不起你。思路就是把一个城市分成四个点，同一个城市坐车，不同城市坐飞机，得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra，所以我就写的dijkstra。#de...