题解：P7984 [USACO21DEC] Tickets P

Tmbcan · 2024-11-18 17:10:14 · 题解

P7984 [USACO21DEC] Tickets P

思路

把每张票都看作一个节点，能买到票的检查站 c_i 向票连权值为 p_i 的边，票向能到达的检查站 [a_i,b_i] 连权值为 0 的边。

现在统计答案，需要求对于每个节点 i 的最短路 dis_{1,i} 和 dis_{i,n}，我们可以建反边分别跑以 1 和 n 为起点的最短路。

然后考虑如何合并答案。由于路径上重复经过的边只会累加一次代价，所以此时 dis_{1,i}+dis_{i,n} 并不是最终答案，因为可能存在重复计算了代价的边。

令 g_i 表示点 i 的最终答案，则 g_i\le dis_{1,i}+dis_{i,n}。
设 S_i 为点 i 答案中重复统计了的点的点集。
当 S_i=\varnothing 时，g_i=dis_{1,i}+dis_{i,n}。
当 S_i\ne\varnothing 时，总存在 u\in S_i 使得 S_u=\varnothing，此时 g_u=dis_{1,u}+dis_{u,n}。对于边 u\to v，当确定了 g_u 后，g_v=\min(g_v,g_u+w_{u\to v})。
我们发现这个转移和最短路的转移一模一样。
所以我们初始时假设每个点都没有重复计算的代价，令 g_i=dis_{1,i}+dis_{i,n}，最后再跑一遍最短路求 g。

由于要对连续的区间连边，所以用 DS 优化建图。