Trouble of Tyrant

题意：1到i有直达的边，i到i-1也有连接的边，问每条边加d后的最短路径的长度。

#include <iostream>
#include <cstdio>
#include <cstdlib>using namespace std;
/*代码来自tangent(谭）*/
/*最小加长距离必然是从最短距离路径的转折点往后移动而增加的，每次扫描当前转折点到最后一个点
来找下一个最小加长距离的转折点，重复直至转折点移动到最后一个点即可。当最小加长距离增加到某个值以后，
就只能选择1到n的直达路径*/
/*不同路径的边数不同，边数越多则加的总值越大，题目求加值后的最短路径，暴力超时，需要像tangent（KEB）这样打表求解*/
/*以目前在下的代码能力，实现起来需要花大量时间，不掌握了，先停留在理解层面*/
struct road
{long long len;int num;long long val;
};struct road home[100100];
long long dis[100100];
long long pas[100100];int erfen(double n,int l,int r)
{int mid=(l+r)/2;if (home[r].val<=n)  return r;if (home[mid].val>n) return erfen(n,l,mid-1);else if (home[mid+1].val>n) return mid;else return erfen(n,mid+1,r);
}int main()
{int t;int i,j,n,q,k,l;long long sum,mini,ans,adds,cha,a,b;scanf("%d",&t);while (t--){scanf("%d%d",&n,&q);for (i=0;i<n-1;i++){//1到i的路径scanf("%lld",&dis[i]);}for (i=0;i<n-2;i++){//i到i-1的路径scanf("%lld",&pas[i]);}mini=dis[n-2];//1到n的路径k=n-2;sum=0;for (i=n-3;i>=0;i--){//找出最短的路径sum+=pas[i];//i到i-1的路径dis[i]+=sum;//i到1的路径if (mini>dis[i]){//保留最短路径mini=dis[i];k=i;//转折点}}j=0;home[j].len=dis[k];//最短距离home[j].num=k;//转折点home[j].val=0;//加0时while (k<n-2){//转折点往后移动mini=dis[n-2]-dis[k];//直达比最短长多少l=n-2;//初始化lfor (i=k+1;i<n-1;i++)//转折点往后移动，找到最小加长距离{a=dis[i]-home[j].len;//转折点为i时，比上个转折点长多少b=i-home[j].num;//找到下一个转折点增加的边数cha=a/b;//最小加长距离if (a%b)//不是整数+1cha++;if (cha<mini){mini=cha;l=i;}if (cha==mini){if (dis[l]+(n-1-l)*cha>dis[i]+(n-1-i)*cha)//l=i;}}k=l;//保存转折点j++;//下一个home[j].len=dis[k];//转折点为k的初始值home[j].num=k;//路的条数a=dis[k]-home[j-1].len;//计算最小加长距离b=k-home[j-1].num;cha=a/b;if (a%b)cha++;home[j].val=cha;//最小加长距离}while (q--){scanf("%lld",&adds);l=erfen(adds,0,j);ans=home[l].len+(n-1-home[l].num)*adds;//printf("%lld",ans);if (q)printf(" ");}printf("\n");}return 0;
}