NC17861. [NOI2014]购票
描述
输入描述
第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。
输出描述
输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。
示例1
输入:
7 3 1 2 20 0 3 1 5 10 100 5 2 4 10 10 10 2 9 1 100 10 3 5 20 100 10 4 4 20 0 10
输出:
40 150 70 149 300 150
C++(clang++ 11.0.1) 解法, 执行用时: 466ms, 内存消耗: 27392K, 提交时间: 2022-08-28 20:12:13
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005,inf=1e9;
int n,t,c,cnt,top,tpp,tsiz,maxx;
int fth[N],p[N],noww[N],goal[N],siz[N],vis[N],stk[N],sta[N];
long long len[N],val[N],dis[N],pr1[N],pr2[N],lim[N],dp[N],rd;
bool cmp(int a,int b)
{
return dis[a]-lim[a]>dis[b]-lim[b];
}
double Slope(int a,int b)
{
return (double)(dp[b]-dp[a])/(double)(dis[b]-dis[a]);
}
void Link(int f,int t,long long v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void Getdis(int nde)
{
for(int i=p[nde];i;i=noww[i])
dis[goal[i]]=dis[nde]+val[i],Getdis(goal[i]);
}
void Mark(int nde,int sze)
{
siz[nde]=1; int tmp=0;
for(int i=p[nde];i;i=noww[i])
if(!vis[goal[i]])
{
Mark(goal[i],sze);
siz[nde]+=siz[goal[i]];
tmp=max(tmp,siz[goal[i]]);
}
tmp=max(tmp,sze-siz[nde]);
if(tmp<=maxx) maxx=tmp,c=nde;
}
void DFS(int nde)
{
stk[++top]=nde;
for(int i=p[nde];i;i=noww[i])
if(!vis[goal[i]]) DFS(goal[i]);
}
void DP(int nde,int anc)
{
for(int i=1;i<=top;i++)
{
int nod=stk[i];
while(nde!=fth[anc]&&dis[nod]-dis[nde]<=lim[nod])
{
while(tpp>=2&&Slope(sta[tpp],nde)>=Slope(sta[tpp-1],sta[tpp]))
tpp--; sta[++tpp]=nde,nde=fth[nde];
}
if(tpp)
{
int l=1,r=tpp,best;
while(l<=r)
{
int mid=(l+r)/2;
double s=(mid==tpp)?-inf:Slope(sta[mid],sta[mid+1]);
if(s<=pr1[nod]) r=mid-1,best=mid; else l=mid+1;
}
best=sta[best],dp[nod]=min(dp[nod],dp[best]+(dis[nod]-dis[best])*pr1[nod]+pr2[nod]);
}
}
}
void PDC(int nde,int sze)
{
if(sze<=1) return;
maxx=inf,Mark(nde,sze); int hc=c;
for(int i=p[hc];i;i=noww[i])
vis[goal[i]]=true,sze-=siz[goal[i]];
PDC(nde,sze),top=0;
for(int i=p[hc];i;i=noww[i]) DFS(goal[i]);
sort(stk+1,stk+1+top,cmp),tpp=0,DP(hc,nde);
for(int i=p[hc];i;i=noww[i]) PDC(goal[i],siz[goal[i]]);
}
int main()
{
scanf("%d%d",&n,&t);
for(int i=2;i<=n;i++)
{
scanf("%d%lld",&fth[i],&rd),Link(fth[i],i,rd);
scanf("%lld%lld%lld",&pr1[i],&pr2[i],&lim[i]),dp[i]=1e18;
}
Getdis(1),PDC(1,n);
for(int i=2;i<=n;i++) printf("%lld\n",dp[i]);
return 0;
}