[PA 2012 Finals] Tax

题目大意

给定一个 \(n\) 个点 \(m\) 条边的无向图，定义路径的代价如下：

经过一个中间点时，代价为 \(max(\) 进入该点的边权, 离开该点的边权 \()\)。
起点 \(1\) 的代价为离开起点的边权
终点 \(n\) 的代价为进入终点的边权
求从点 \(1\) 到点 \(n\) 的最小代价。

数据范围： \(n\le10^5,m\le2\times10^5,1\le c\le10^6,n\le10^5,m\le2\times10^5,1\le c\le10^6\)

算法分析

这道题与普通最短路最大的不同在于：代价不是边权之和，而是相邻两条边权取后再求和。也就是说，代价取决于边的组合而非单条边。

这导致我们无法直接在原图上跑 Dijkstra，因为到达同一个点时，从哪条边进来会影响后续的代价计算，状态不能简单合并。

化边为点

既然代价取决于边的组合，一个自然的想法是：把原图的每条边看作新图的一个点，两条边如果在原图中首尾相连（即存在公共端点），就在新图中连边，边权为两条边权值的。

具体操作：

1. 将每条无向边 \(u,v,w\) 拆成两条有向边：\(u\rightarrow v\) 和 \(v\rightarrow u\)。

2. 对于原图中两条有向边 \(a:u\rightarrow v\) 和 \(b:v\rightarrow u\)(\(a\) 的终点 \(b\) 的起点)，在新图中从点 \(a\) 向点 \(b\) 连一条有向边，权值为 \(max(a_w,b_w)\)。

3. 新建超级源点 \(S\)：从 \(S\) 向所有从点 \(1\) 出发的有向边连边，权值为该边的边权(起点代价)。

4. 新建超级汇点 \(T\)：从所有指向点 \(n\) 的有向边向 \(T\) 连边，权值为该边的边权(终点代价)。

5. 在新图上跑 \(S\rightarrow T\) 的最短路即为答案。

但是给你个菊花图那你不就炸了。

差分优化建图

我们需要把每个点周围的边压缩到原来的一半。

核心观察：对于原图某个点 \(v\)，设其所有出边按边权从小到大排序为 \(e_1,e_2,…,e_k\)(权值分别为 \(1_w\le 2_w\le⋯\le k_w\))。

若从边 \(e_i\) 进入 \(v\)，从边 \(e_j\) 离开 \(v\)(\(i\le j\))，则代价为 \(max⁡(i_w,j_w)=j_w\)。这个值可以拆解为：

\(j_w=i_w+(i_w+1−i_w)+(i_w+2−i_w+1)+⋯+(j_w−j_w−1)\)

建图方法：对每个点 \(v\) 的所有出边按权值排序后：

相邻两条边 \(e_i\rightarrow e_i+1\) 连一条有向边，权值为 \(wi+1−wi\)(正向差分边)。
相邻两条边 \(e_i+1\rightarrow e_i\) 连一条有向边，权值为 \(0\)(反向零权边)。
对于每条有向边 \(u\rightarrow v\)(权值 \(w\))，从其反向边 \(v\rightarrow u\) 向 \(u\rightarrow v\) 连一条权值为 \(w\) 的边(表示进入该点时需要支付的基础代价)。
为什么这样是对的？

假设从边 \(p\) （权值 \(p_w\) ）进入点 \(v\)，要从边 \(q\)(权值 \(q_w\))离开：

若 \(p_w\le q_w\)：先从反向边走到 \(p\) （代价 \(p_w\) ），然后沿着正向差分边一路走到 \(q\)，总代价 \(=p_w+(q_w−p_w)=q_w=max⁡(p_w,q_w)\)。
若 \(p_w>q_w\)：先从反向边走到 \(p\) （代价 \(p_w\) ），然后沿着反向零权边走到 \(q\)，总代价 \(=p_w+0=p_w=max⁡(p_w,q_w)\)。
这样，每个点周围的边数降了一半，总边数为 \(O(m)\) 级别。