标签-最短路

题意给出一个有点权的无向图,有的节点有酒吧。从起点出发,需要找到以酒吧为终点的路径,每个节点可以经过任意次,求路径上点权和的最大值。其中点数 $N\le 500000$ ,边数 $M\le 500000$ 。题解缩点,转化为DAG后跑最长路即可。最后取有酒吧的节点中最长路的最大值。#include<bits/stdc++.h> using namespace std; inl...
   题解    0 条评论
提高+/省选-
题意给一个有向图,如果有负权回路输出-1,否则输出从起点 $S$ 到各个点的最短路长度,如果不连通输出NoPath。其中点数 $N\le 1000$ ,边数 $M\le 100000$ 。题解做法很显然,就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环,求最短路就顺便继续用,然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ,但我又不想删判负环的所以就写了两个。#includ...
   题解    0 条评论
题意给出一个有向图,需要从 $1$ 走到 $N$ ,可以在一个城市买水晶球并在另一个城市卖掉,也可以不买,问最多能赚多少钱。其中 点数$n\le 100000$ ,边数$m\le 500000$ 。题解分层图最短路。对于原图,买卖操作各建一层图,边权为在起点买卖水晶球的花费(买为负卖为正)。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ,对于每...
   题解    0 条评论
提高+/省选-
题意给一个无向图,求严格次小最短路。其中点数 $N\le 5000$ ,边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较,将较小值给最短路,较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重,可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
   题解    0 条评论
提高+/省选-
题意求 从$1$ 到 $N$ 的一条路径,使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ,边数 $P\le 2000$,权值 $L_i\le 10^{6}$题解直接求肯定没有办法,所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分,每次检验就跑一次 $Dijkstra$ ,只是把边权变为 $>x$ 的边的条数,这样就可以得到$>x$ 的边最少...
   题解    0 条评论
提高+/省选-
卧槽竟然一遍就A了,可把身为蒟蒻的我nb坏了刚开始让我做这道题,我是拒绝的,然后看完题发现,这就是道裸的最短路,连边搞就是了。然后发现它只给三个点,看了题解才知道第四个点可以用向量点乘判断垂直来求,路燕我对不起你。思路就是把一个城市分成四个点,同一个城市坐车,不同城市坐飞机,得到所有点的坐标和所在城市以后跑一遍最短路就行了。因为我很菜只会dijkstra,所以我就写的dijkstra。#de...
   题解    0 条评论
提高+/省选-