P14019 题解

容易想到把车站作为点建图跑最短路。

关键在于转车怎么处理，直接连边肯定是不行的：对于一个车站

x

，已知

1

到它的距离

d_x

以及转车系数

b_x

，则转车到

y

的代价为

b_xa_y+d_x

，容易发现这是一个一次函数，关于

a_y

递增。

所以在同一个地方通过“转车”来转移时，一定是

a_y

较小的

y

先转移，并且转移的过程是取若干一次函数（该地点每个已经求出距离的车站都对应一个一次函数）的最小值。

因此在每个地点把对车站按

a

从小到大排序，用李超树维护一次函数最小值。每次求出一个车站的距离后更新李超树，对于它所在地点找到

a_y

最小的车站

y

，求出

y

对应的最小值放进堆里即可。

时间复杂度是一只

\log

。代码里面的

a,b

是反过来的。

CPP

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
int n,m;
int a[200005], b[200005];

struct Node{
	int id,c,b;
	friend bool operator<(const Node &a,const Node &b){
		return a.b<b.b;
	}
};
vector<Node> zq[200005]; int p[200005];
int pos[400005];

struct Edge{
	int v,c,op; ll w;
	friend bool operator<(const Edge &a,const Edge &b){
		return a.w>b.w;
	}
};
vector<Edge> ed[400005]; int T1;
priority_queue<Edge> q;

struct Line{
	ll k,b;
	inline ll Val(const ll &x){return k*x+b;}
};
const int maxB=1000000;
struct Segtree{
	#define ci const int
	#define ulr int &u,ci &lp,ci &rp
	#define ls lc[u]
	#define lc_ ls,lp,mid
	#define rs rc[u]
	#define rc_ rs,mid+1,rp
	#define Chl if (Li.Val(lp)<li[u].Val(lp))
	#define Chr if (Li.Val(rp)<li[u].Val(rp))
	#define dmid int mid=lp+(rp-lp)/2
	Line li[600005];
	int lc[600005], rc[600005];
	int Rt[200005], T1;
	void modify(ulr,Line Li){
		if (!u) return li[u=++T1]=Li, void();
		dmid; if (li[u].Val(mid)>Li.Val(mid)) swap(li[u], Li);
		Chl modify(lc_,Li); Chr modify(rc_,Li);
		return ;
	}
	ll query(ulr,ci &p){
		if (!u) return inf;
		dmid; if (p<=mid) return min(query(lc_,p),li[u].Val(p));
		return min(query(rc_,p),li[u].Val(p));
	}
}Tr1;

ll dis[400005];
ll ddis[200005];

int main(){
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d",b+i);
	for (int i=1;i<=m;i++) scanf("%d",a+i);
	for (int i=1;i<=m;i++){
		int d, s; scanf("%d %d",&d, &s);
		zq[s].push_back((Node){++T1,i,b[i]}); pos[T1]=s; s=T1;
		for (int j=2;j<=d;j++){
			int w,v; scanf("%d %d",&w,&v);
			zq[v].push_back((Node){++T1,i,b[i]});
			ed[s].push_back((Edge){T1,i,0,w}); pos[T1]=v; s=T1;
		}
	}
	for (int i=1;i<=n;i++) sort(zq[i].begin(), zq[i].end());
	memset(dis,0x3f,sizeof(dis)); memset(ddis,0x3f,sizeof(ddis)); 
	for (auto Nd:zq[1]) q.push((Edge){Nd.id,Nd.c,0,0});
	while (!q.empty()){
		auto Edd=q.top(); q.pop();
		int u=Edd.v, c=Edd.c, op=Edd.op; ll w=Edd.w; 
		if (dis[u]!=inf||w==inf) continue;
		int po=pos[u]; ddis[po]=min(ddis[po],w); dis[u]=min(dis[u],w);
		for (auto Ed:ed[u]) q.push((Edge){Ed.v,c,0,w+Ed.w});
		
		while (p[po]<zq[po].size()&&dis[zq[po][p[po]].id]!=inf) p[po]++;
		if (p[po]==zq[po].size()) continue;
		Tr1.modify(Tr1.Rt[po],1,maxB,(Line){a[c],w});
		auto Nd=zq[po][p[po]]; 
		q.push((Edge){Nd.id,Nd.c,1, Tr1.query(Tr1.Rt[po],1,maxB,Nd.b)});
	}
	for (int i=2;i<=n;i++) printf("%lld ",ddis[i]);
	return 0;
}

文章操作

相关推荐

评论

P14019 题解