做题笔记 - 最短路

Roads and Gates

来源：AT_abc463_e

难度：1055

这场 D 和 E 自己做的方法好麻烦，导致没时间做 F 和 G。

提供一个别于建两个虚点的思路。对于特殊边而言，若真的建出 $\frac{1}{2}n(n-1)$ 条双向边，发现边数会爆炸。所以不可行。

考虑一下将 $\frac{1}{2}n(n-1)$ 条边不直接建出来，显然这之中大部分边是没用的。注意到 $w_{i,j}=x_i+Y+x_j$，观察 Dijkstra 的过程，对于已经找到最小值的点集 $S$，和尚未找到最小值的点集 $T$，显然有 $S\cap T=\varnothing,S\cup T=V$，下一个更新 $\text{dis}$ 的点必然是由 $S$ 中某一点 $u$ 所连一条边的另外一个端点 $v$，且 $v\in T$。实际上，对于特殊边，也是一样的。考虑 Dijkstra 堆优化每一次实际是把 $\text{dis}$ 最小的点拿出来，对于 $x_u+Y$ 的部分只要找到 $S$ 的某一个点使其最小即可，$x_v$ 的部分同理，那么我们在 Dijkstra 贪心过程中，每当 $S$ 发生变化，即找到一个点 $u$ 的 $\text{dis}$ 确定了，可以把这条没有建出来的边扔到堆里，实际上只会新增 $n-1$ 条虚边。

void dijkstra(int S){
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pli>q;
	dis[S]=0;
	q.push(mkp(-dis[S],S));
	ll minn=x[1]; // 记录集合 S 的最小 dis_u + x_u
	while(!q.empty()){
		int u=q.top().se;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		Min(minn,dis[u]+x[u]);
		s.erase(mkp(x[u],u)); // 将 u 移出集合 T
		for(auto it:E[u]){
			int v=it.v,w=it.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(mkp(-dis[v],v));
			}
		}
        
		if(!s.empty()){ 
			auto it=*s.begin();
			int v=it.se;
			if(dis[v]>minn+y+x[v]){ // 找到连接 S - T 的最短特殊边
				dis[v]=minn+y+x[v];
				q.push(mkp(-dis[v],v));
			}
		}
	}
}