CF1163F - Indecisive Taxi Fee 题解

假设不经过边 \(t\) 的最短路为 \(D_t\)，经过的为 \(B_t\)，那么答案显然为 \(\min(D_t,B_t-w_t+x)\)。我们只要对每条边把这两者求出来即可。

dij 求出 \(1\to n\) 的任意一条最短路 \(p_{1\sim s}\)，如果 \(t\) 不在其上的话，显然必有 \(D_t=\mathrm{dis}(1,n)\)，\(B_t=\min(\mathrm{dis}(1,a_t)+w_t+\mathrm{dis}(b_t,n),\mathrm{dis}(1,b_t)+w_t+\mathrm{dis}(a_t,n))\)??，?而 \(\mathrm{dis}(1,\cdot),\mathrm{dis}(\cdot,n)\) 可以两遍 dij 求出。如果 \(t\) 在其上，那么显然 \(B_t=\mathrm{dis}(1,n)\)，而 \(D_t\) 是整张图删掉 \(t\) 之后的最短路（事重头戏）。

下面来介绍一下删边最短路的科技（称为科技是因为感觉凭自己想不出来/kk）。首先，\(p\) 既是 \(1\to n\) 的最短路也事 \(n\to 1\) 的最短路，固定住它只考虑删其上的边。显然有结论：\(1\to x\)? 的所有最短路中必定存在一条与 \(p\) 共享且仅共享一个前缀（可以取最后一个交点，也可用最短路生成树证），\(x\to n\)、后缀也如此。假设前后缀端点在 \(p\) 上的下标为 \(pre_x,suf_x\)，这显然可以建出最短路树 dfs 一遍求出。但要求 \(1\) 为起点、\(n\) 为起点的最短路树中 \(1\leftrightarrow n\) 路径都是 \(p\)，这可以在建 \(n\) 树时对于最短路上的点强制连边。

以及显然地，删除 \(t\) 后的最短路一定是先共享 \(p\) 的一段前缀（但不跨过 \(t\)），然后腾空一段弧绕过 \(t\)，最后回到 \(p\) 上共享 \(p\) 的后缀（很好证，\(t\) 两边取最迟、早的交点调整）。接下来是最关键的结论：中间这段腾空的弧里，恰好有（显然至少有）一条非最短路树边。也就是说，设弧的两端在 \(p\) 上的下标为 \(x,y\)，恰好存在边 \(e\) 使得 \(pre_{a_e}=x,suf_{b_e}=y\)（当然 \(a,b\) 有可能互换）。

考虑反证。假设有至少两条非树边，取任意相邻的两条 \(e,f\)??，?如下图：

我们考虑 \(1\to b_e\) 的最短路，\(pre_{b_e}\) 必然不可能在 \(t\) 左侧，那样直接走 \(1\to b_e\) 的最短路而非 \(1\to a_e\overset{e}{\to} b_e\) 显然会更优；\(n\to a_f\) 也事如此，\(suf_{a_f}\) 一定在 \(t\) 左侧。如下图：

考虑证明这种情况不存在。我们知道 \(D\)? 是两端的最短路（因为 \(e,f\)? 之间不再有非树边），跟据最短路的拼接定理可知 \(\mathrm{dis}(1,a_f)=D+\mathrm{dis}(1,b_e)=\mathrm{dis}(1,suf_{a_f})+C+B+D\)?。而另一条路 \(\mathrm{dis}(1,suf_{a_f})+A\)? 不是最短路，说明 \(C+B+D\leq A\)?。同理，考虑 \(b_e\to n\)? 最短路可得 \(C+A+D\leq B\)?。可知 \(A-B\)? 和 \(B-A\)? 都大于等于 \(C+D\)?，而 \(C+D\)? 事正数，事不可能同时被一个数和它的相反数大于等于的，矛盾！证毕。

这样的话，枚举所有非 \(p\)? 中边作为弧上的唯一非树边 \(e\)?，贡献到 \(p\)? 上的下标区间 \([pre_{a_e},suf_{b_e}]\)?，贡献值为 \(\mathrm{dis}(1,a_e)+w_e+\mathrm{dis}(b_e,n)\)?；以及需要交换 \(a,b\) 再做一次。这可以线段树，但是事静态的可以直接差分 multiset。于是删边最短路就做完了。

#include
using namespace std;
#define int long long
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10;
int n,m,qu;
int a[N],b[N],w[N];
vector > nei[N];
int d1[N],dn[N];
int vis[N];
void dij(int st,int d[]){
	for(int i=1;i<=n;i++)d[i]=inf;
	memset(vis,0,sizeof(vis));
	priority_queue,vector >,greater > > q;
	q.push(mp(d[st]=0,st));
	while(q.size()){
		int x=q.top().Y;q.pop();
		if(vis[x])continue;vis[x]=true;
		for(int i=0;i son1[N],sonn[N];
int ord[N];
bool cmp(int x,int y){return d1[x] ton;int id[N];
int pre[N],suf[N];
void dfs(int x,int las,int p[],vector vec[]){
	if(~id[x])las=id[x];
	p[x]=las;
	for(int i=0;i add[N],del[N];
signed main(){
	cin>>n>>m>>qu;
	for(int i=1;i<=m;i++)scanf("%lld%lld%lld",a+i,b+i,w+i),nei[a[i]].pb(mp(b[i],i)),nei[b[i]].pb(mp(a[i],i));
	dij(1,d1),dij(n,dn);
	for(int i=1;i<=n;i++)ord[i]=i;
	sort(ord+1,ord+n+1,cmp);
	for(int _i=2;_i<=n;_i++){
		int i=ord[_i];
		for(int j=0;j st;
	for(int i=0;i+1