题意给出一个 $n(\le 1000)$ 点 $m(\le 10^6)$ 边的有向图，求 $1\rightarrow n$ 的边权积最小的路径。题解因为需要松弛所以不能取模，如果直接乘起来又会爆。不过 $\log(a\times b)=\log(a)+\log(b)$ ，可以改为求边权为 $\log(w)$ 的最短路。在最短路过程中记录 $y$ 的上一个点 $lst[v]$ 以及两点之间的真...
题意有 $n(\le 1000)$ 个人，每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ，要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ，如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。求最大的 $T$ ，使得限制变为 $s[A] > s[B]\times (k-T)$...
双倍经验：洛谷4568，只需要改数据范围。题意有一个 $n(n\le 10000)$ 点 $m(m\le 50000)$ 边的无向图，可以将其中 $k(k\le 20)$ 条边的边权改成 $0$ ，求 $1\rightarrow n$ 的最短路。题解分层图最短路。将图分为 $k+1$ 层，同一层按给出的边连边；第 $i$ 层与第 $i+1$ 层之间也按给出的边连，但权值为 $0$ 。这样走到...
题意有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图，有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ （保证可以到达）。每个点都有些时刻无法通行，如果更换道路还需要额外交 $k$ 元。求最小花费。题解用 $f[i]$ 表示前 $i$ 个时刻的最小花费，$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ，可以得到方程：$$f[i]=\...
题意给出一个 $N$ 点 $M$ 边的有向图，以及 $K$ 个感兴趣的点，求感兴趣的点两两之间最短路的最小值。$N\le 100000 \ , \ M\le 500000$ 。题解如果建立原点和汇点，把 $K$ 个点分成两组，分别与原点汇点相连，再从原点开始跑到汇点的最短路就是最小值。但这样显然无法涵盖所有情况。所以枚举二进制位，把当前位为 $1$ 的加入第一组，其它的放入第二组。因为两个数...
题意给出一个 $N$ 点 $M$ 边的有向图，并给出最短路径。依次删掉最短路上的每条边，求删边后最短路长度。$N\le 10^5 \ , \ M\le 2\times 10^5$ 。题解朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ，但这样显然会爆。可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ，那么最短路一定是 $$1\rightarrow x\righ...
题意给出一个 $N$ 点 $M$ 边的有向图，要从 $1\rightarrow D$ 。每条边上有限速，如果限速为 $0$ 则需要按照上一条边的速度走。求最短用时。$N\le 150$ 。题解给朴素的最短路加上一维，用 $dis[x][s]$ 表示在节点 $x$ ，当前速度为 $s$ 的最短用时。然后跑 $\text{Spfa}$ 即可。tips: 对 double 进行 memset 时最...
题意给出一个 $N$ 点无向图，至少有两个连通块。求连接两个连通块的方案，使得新连通块的直径最小。$N\le 150$ 。题解先用 $\text{Floyd}$ 跑最短路，然后可以算出从每个点出发的最远距离，然后枚举两个不连通的点连上即可得到答案。但有可能出现连接的两个点不是直径两端的情况，这时原来连通块的直径就是这个新连通块的直径，所以需要取最大值。#include<bits/std...
题意要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ，每秒可以走 $2^k$ 条边（$k$ 是任意自然数），求最少要花多少秒。$N\le 50 \ , \ M\le 10000$ 。题解用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ，可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$...
2021.11.18更新：“最长路径 $+1$ 就是答案”有误，因为对于 $M_2$ 的情况，两点间的距离其实可以是无穷大的。但强连通分量中就不会有这种情况，因为点之间两两互通，所以它们之间的距离也就有上限。题意有 $N$ 个数和 $M_1+M_2$ 种关系。前 $M_1$ 种关系 $(x,y)$ 表示 $S_x+1=S_y$ ，后 $M_2$ 种关系表示 $S_x\le S_y$ 。求最多...
题意令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目，$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目；则定义：$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$其中点数 $n\le 100$ ，边数 $m\le 4500$ 。题解$n\le 100$ ，又要统计所有节...
题意给出一张无向连通图，求 $S$ 到 $E$ 经过 $N$ 条边的最短路。其中边数 $T\le 100$ ，点的编号 $\le 1000$ ，$N\le 10^6$ 。题解因为是连通图，所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。考虑 $\text{Floyd}$ 的过程：$$\text{dis[i][j]}=\min...
题意给出一个 $n$ 点 $m$ 边的有向图，从 $1$ 出发再回到 $1$ ，途中要逆行一次，问途中最多经过多少个点。$n,m\le 10^{5}$ 。题解显然要缩点，缩点后点权即为连通分量中点的个数 $\text{siz[]}$ 。然后对强连通分量重新建边，正边为 $\text{edge2}$ ，反边为 $\text{edge3}$ 。对正边跑最长路得到以 $1$ 为起点的最长路 $\t...
题意给出一个有点权的无向图，有的节点有酒吧。从起点出发，需要找到以酒吧为终点的路径，每个节点可以经过任意次，求路径上点权和的最大值。其中点数 $N\le 500000$ ，边数 $M\le 500000$ 。题解缩点，转化为DAG后跑最长路即可。最后取有酒吧的节点中最长路的最大值。#include<bits/stdc++.h>
using namespace std;
inl...
题意给一个有向图，如果有负权回路输出-1，否则输出从起点 $S$ 到各个点的最短路长度，如果不连通输出NoPath。其中点数 $N\le 1000$ ，边数 $M\le 100000$ 。题解做法很显然，就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环，求最短路就顺便继续用，然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ，但我又不想删判负环的所以就写了两个。#includ...