T1
• 在 \(N\) 个点 \(P\) 条边的加权无向图上求出一条从 \(1\) 号结点到 \(N\) 号结点的路径，使路径上第 \(K + 1\) 大的边权尽量小。
• \(0 ≤ K < N ≤ 1000\), \(1 ≤ P ≤ 2000\)。
Solution
• 一道自己做出来的蓝。
• 二分第 \(K + 1\) 大边权为 \(mid\)，每次把边权 \(\leq mid\) 的都设为 \(0\)，否则设为 \(1\)。
• 从节点 \(1\) 跑一次最短路，当 \(dist[n] \leq mid\) 时则满足条件，否则不满足。
• 正确性显然。
T2
• 树形黑暗城堡有 \(N\) 个房间，\(M\) 条可以制造的双向通道，以
及每条通道的长度。
• 设 \(D_i\) 为如果所有的通道都被修建，第 \(i\) 号房间与第 \(1\) 号房间的最短路径长度；
• 而 \(S_i\) 为实际修建的树形城堡中第 \(i\) 号房间与第 \(1\) 号房间的路径长度；
• 要求对于所有整数 \(i\) \((1 ≤ i ≤ N)\)，有 \(S_i = D_i\) 成立。
• 有多少种不同的城堡修建方案，答案对 \(2 ^ {31} − 1\) 取模。
Solution
• 简单来说，题目要求最短路径树的数量。
• 最短路径树是网络的源点到所有结点的最短路径构成的树。
• 我们从节点 \(1\) 跑一遍最短路。
• 当 \(dist[v] = dist[u] + e(u, v)\) 时，表明 \(v\) 的最短路是由 \(u\) 得到的，那 \(e(u, v)\) 就可以作为最短路径树上的边。
• 对每个点计算出它可作为最短路径树上的边的数量，根据乘法原理，乘起来就是答案。
T3
• 要给 \(n\) 口矿井供电。
• 为了保证电力的供应，有两种办法：
\(1.\) 在这一口矿井上建立一个发电站，费用为 \(v\)。
\(2.\) 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 \(p\)。
• 计算保证所有矿井电力供应的最小花费。
• \(1 ≤ n ≤ 300\), \(0 ≤ vi, p_{ij} ≤ 10^5\)。
Solution
• 简单来说，要使每个点所在的联通块的都至少有一个发电站的最小花费。
• 建立一个虚拟源点 \(0\)，给每口矿井连一条边权为 \(v_i\) 的边，跑一遍最小生成树即可。
T4
• \(N\) 头牛（每头牛的编号就是它所在农场的编号）要去参加一场在编号为 \(x\) 的牛的农场举行的派对。
• 有 \(M\) 条有向道路，每条路长 \(T_i\)；
• 每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。
• 求这 \(N\) 头牛的最短路径（一个来回）中最长的一条的长度。
• \(1 ≤ N ≤ 1000\)，\(1 ≤ x ≤ N\)。
• \(1 ≤ M ≤ 100000\)，\(1 ≤ T_i ≤ 100\)。
Solution
• 扇贝题目。
• 先跑一遍各点到 \(x\) 的距离，然后再跑一遍 \(x\) 到各点的距离即可。
• 但是朴素做法，虽然可以通过此题，但我们考虑优化。
• 建立正图和反图，都以 \(x\) 为起点，预处理出到每个点的最短路 \(d_1\) 和 \(d_2\)。
• 正图 \(d_1\) 为回家路，反图 \(d_2\) 为去 \(x\) 的路。
• 枚举每个点的 \(d_1 + d_2\)，取最大值即可。
T5
• \(N\) 个点 \(M\) 条边的有向图，边有黑白两种颜色。现在要给点染色，每个点染成黑或白色。
• 白点只能走它连出去的白边，黑点只能走它连出去的黑边。
• 问是否存在一种染色方案，使得不存在一条 \(1 → n\) 的路径。如果存在这样的染色方案，在第一行输出 \(−1\)，否则输出 \(→ n\) 最长的最短路径长度，每条边长度为 \(1\) 。在第二行，输出对应第一行答案的染色方案。
• \(1 ≤ N, M ≤ 500000\)。
Solution
• 考虑从 \(n\) 出发进行染色，尽可能让每一条路不可经过，这样也是最大化其他点到 \(n\) 的最短路。
• 如果当前为 \(u\) ，点 \(v\) 和 \(u\) 有边，如果只有一种颜色的边，那么这条路是可以禁止经过的，将 \(v\) 设置成与边不同的颜色。如果有不同颜色的边，那么 \(v\) 的颜色无论怎么染色都可以到达 \(u\)。
• 从 \(n\) 开始进行反向 BFS 。
• 当第一次遍历到未染色的点 \(x\)，将点 \(x\) 设为与边不同的颜色。如果遍历到染色的点，并且染色的点与边颜色相同，说明此点无法避开，加入到队列中，更新到 \(n\) 的最短路，直到 \(1\) 入队。
• 时间复杂度为 \(\mathcal{O}(N + M)\)
T6
• 在一个有 \(N\) 个顶点和 \(M\) 条边的图上有两个人，分别在 \(S\) 号节点和 \(T\) 号节点。他们要各自走到对面（即在 \(S\) 的人走到 \(T\) ，在 \(T\) 的人走到 \(S\)）。
• 给你 \(M\) 条边，描述为 \(U\) \(V\) \(D\) 分别表示该边连接的两个点及通过边的时间。
• 求两人经过最短路径（可能有多条）且不相遇（在同一单位时间内都在一条边或一个点上）的方案数。
• \(N ≤ 100000，M ≤ 200000\)。
Solution
咕咕咕。
T6
• 有一个地铁线路图，可以看做 \(N\) 个站点，\(M\) 条线路。每条线路由一个公司所有。
• 如果你乘坐同一公司的铁路，只需要花费 \(1\) 元，如果更换其他公司铁路，还需要再花费 \(1\) 元，如果再次换回原来的公司，还需要花费 \(1\) 元。
• 问从 \(1\) 号站点到 \(N\) 号站点的最小花费。
• \(N, M ≤ 200000\)。
Solution
• 由于切换连通块一定会导致答案 \(+1\)，因此只要统计连通块的个数即可。
• 最朴素的建图方式是：把连在一起的同一城市的道路两端的点放进一个连通块内，块内每个点两两之间连一条权值为 \(1\) 的边。但是，边数过大，这样会爆空间。
• 考虑优化。
• 尝试建立虚点。
• 对于每个连通块，建立一个虚点。把连通块内每个点和虚点连一条权值为 \(0.5\) 的边。这样，任意两点都能以虚点为中转站来保持距离仍为 \(1\)。
• 优化后，点的数量不超过 \(n + m\)，边的数量不超过 \(2m\)。