P7984 [USACO21DEC] Tickets P

比较直接的双老哥做法。

前置知识：线段树优化建图。

solution

对于每个点都求到 $1,n$ 的最短路太困难了，考虑（建反图）转而求 $1,n$ 到每个点的最短路。分别求出 $1,n$ 到每个点的最短路，记为 $dis$ 和 $dis'$。那么对于每个点 $u$ 来说答案的上界就是 $dis_u+dis_u'$。

考虑什么时候会算多。那么一定是走了一段相同的路，付了两次钱。

同时我们断言，这一段相同的路只会是最后一段（而不可能在前面有其它段走了相同的路），形如 Y 型（下图）。

证明比较显然：如果在更前的地方走了一段相同的，后面再分叉，一定不如直接一起走到终点。

于是答案式子为：$ans_v=\min\{dis_v+dis_v',\min_u (ans_u+w_{u,v})\}$。

这仍然是一个最短路的形式。所以在求完 $dis,dis'$ 后，从一个超级源点向所有点建边权为 $dis+dis'$ 的边，再跑一次最短路即可求出答案。

现在只需要解决一个区间向一个点连边，求最短路的问题。线段树优化建图即可。

复杂度 $O(n\log^2 n)$。

code

非常需要注意的是，你需要给每张票建一个虚点，而不是直接把一个区间连向买票的点，否则因为线段树把这个区间拆成了很多小区间，你可能会给每个小区间额外付一次费。详见：@ MeowScore 的警示帖。

非常好写。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100006,maxd=(maxn<<3);
int n,q,S,tot;
int tik[maxn],dot[maxn];
struct Edge{
	int to,nxt;ll w;
}edg[maxd<<3];
int hd[maxd],tt;
inline void add(int u,int v,ll w){edg[++tt]={v,hd[u],w};hd[u]=tt;}
namespace Segtree{
	int l[maxd],r[maxd],id[maxd];
	#define mid (l[p]+r[p]>>1)
	#define ls (p<<1)
	#define rs (p<<1|1)
	inline void build(int p,int pl,int pr){
		id[p]=++tot;
		l[p]=pl,r[p]=pr;if(pl==pr) return dot[pl]=id[p],void();
		build(ls,pl,mid),build(rs,mid+1,pr);
		add(id[ls],id[p],0),add(id[rs],id[p],0);
	}
	void upd(int p,int ql,int qr,int liz,int val){
		if(ql<=l[p]&&r[p]<=qr){return add(id[p],liz,val);}
		(ql<=mid)&&(upd(ls,ql,qr,liz,val),1121),(mid<qr)&&(upd(rs,ql,qr,liz,val),1121);
	}
}using namespace Segtree;
struct node{
	int u;ll dis;
	bool operator <(const node &qyy)const{return dis>qyy.dis;}
};
priority_queue <node> pq;
bool vis[maxd];
ll de[maxd],dn[maxd],ans[maxd];
inline void dij(int s,ll (&dis)[maxd]){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	while(!pq.empty()) pq.pop();
	pq.push({s,dis[s]=0});
	while(!pq.empty()){
		int u=pq.top().u;pq.pop();
		if(vis[u]) continue;vis[u]=1;
		if(dis[u]>=dis[0]) break;
		for(int e=hd[u],v;e;e=edg[e].nxt){
			v=edg[e].to;if(dis[v]<=dis[u]+edg[e].w) continue;
			dis[v]=dis[u]+edg[e].w;pq.push({v,dis[v]});
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;build(1,1,n);
	for(int i=1,c,p,a,b;i<=q;i++){
		cin>>c>>p>>a>>b;tik[i]=++tot;
		upd(1,a,b,tik[i],0);
		add(tik[i],dot[c],p);
	}S=++tot;
	dij(dot[1],de);dij(dot[n],dn);
	for(int i=1;i<S;i++) add(S,i,de[i]+dn[i]);
	dij(S,ans);
	for(int i=1;i<=n;i++) cout<<(ans[dot[i]]>=ans[0]?-1:ans[dot[i]])<<'\n';
	return 0;
}