题解：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 优化建图。