1548

Day \(\text{叁拾肆}\)。 DS 写不动了，标题也取不动了www。 类似 Day 1 CF1270H Number of Components，每个连通块中选出一个代表的点。令一个连通块内所有点按照 \(v_{i,j}=\{a_i+b_j,i,j\}\) 排序，对最小的 \(v_{i,j ......

## [$POJ$ $1548$ $Robots$](http://poj.org/problem?id=1548) ### 题意 相当于给出$N$个坐标点，因为机器人只能向下或者向右走，所以如果能到达其他点，则连接这两个点，即`line[i][j]=1` **最小路径覆盖数**: 对于一个$DAG ......

题意：第 i 个火车站都有一个数字 Ki (0≤Ki ≤N)，火车在第 i 站只能前进Ki 站或后退 Ki 站。火车只能在第 1 站和第 N 站之间行驶。 请问，从第 a 站到第 b 站最少需前进或后退多少次？ 分析：利用BFS，将每个站出发能到的所有站都入队，不断更新下去，直到所有站都被到达或者车 ......