正题

题目链接:https://loj.ac/p/2769

题目大意

给出\(n\)个点\(m\)条地铁线路，每条线路是一条路径。

求\(1\)到\(n\)的最短路且在最短路径的情况下相邻换乘点的距离平方和最大。

\(1\leq n,m,\sum s_i\leq 10^6\)

解题思路

首先肯定是在最短路树上跑，然后考虑怎么求平方和最大。

因为每条可以计算和的路径一定是连续的一段，所以考虑将一条铁路线去掉不在最短路树上的边后分出若干段来。

对于每一段上的转移都是一个\(f_{x}=max\{f_y+(d_x-d_y)^2\}\)的形式，可以斜率优化。

但是为了充分转移，需要按照\(dis\)从小到大转移。

栈啊什么的开\(vector\)就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#include<cctype>

#define mp(x,y) make_pair(x,y)

#define sec second

#define fir first

#define ll long long

using namespace std;

const ll N=1e6+10;

struct node{

	ll to,next,w;

}a[N];

ll n,m,T,tot,ls[N],dis[N],f[N],top[N],p[N],las[N];

vector<pair<ll,ll> >e[N],E[N],pos[N];

priority_queue<pair<ll,ll> >q;

vector<ll> _x[N],_y[N],s[N];bool v[N];

ll read(){

	ll x=0,f=1;char c=getchar();

	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+c-48;c=getchar();}

	return x*f;

}

void addl(ll x,ll y,ll w){

	a[++tot].to=y;

	a[tot].next=ls[x];

	ls[x]=tot;a[tot].w=w;

	return;

}

void dij(){

	memset(dis,0x3f,sizeof(dis));

	q.push(mp(0,1));dis[1]=0;

	while(!q.empty()){

		ll x=q.top().sec;q.pop();

		if(v[x])continue;v[x]=1;

		for(ll i=ls[x];i;i=a[i].next){

			ll y=a[i].to;

			if(dis[x]+a[i].w<dis[y]){

				dis[y]=dis[x]+a[i].w;

				q.push(mp(-dis[y],y));

			}

		}

	}

	return;

}

bool cmp(ll x,ll y)

{return dis[x]<dis[y];}

double slope(ll x,ll y,ll p)

{return (double)(_y[p][y]-_y[p][x])/(_x[p][y]-_x[p][x]);}

void calc(ll x,ll p,ll t,vector<ll> &s,ll &top){

	//x点 p线 t站

	if(!t)return;

	ll dx=e[p][t].sec;

	while(top>1&&slope(s[top-1],s[top],p)<=2*dx)top--;

	if(top){

		ll y=s[top];

		f[x]=max(f[x],_y[p][y]-2*dx*_x[p][y]+dx*dx);

	}

}

void add(ll x,ll p,ll t,vector<ll> &s,ll &top){

	//x点 p线 t站

	if(t>=e[p].size()-1)return;

	ll dx=e[p][t].sec;

	_y[p][t]=f[x]+dx*dx;_x[p][t]=dx;

	while(top>1&&slope(s[top-1],t,p)>=slope(s[top-1],s[top],p))top--;

	s[++top]=t;las[p]=t;return;

}

signed main()

{

//	freopen("city.in","r",stdin);

//	freopen("city.out","w",stdout);

	n=read();m=read();

	for(ll i=1;i<=m;i++){

		ll num,x,t=0;num=read()+1;

		while(num--){

			if(E[i].size())t=read();x=read();

			if(E[i].size()){

				pair<ll,ll> z=E[i][E[i].size()-1];

				addl(z.fir,x,t);

			}//建边

			E[i].push_back(mp(x,t));

		}

	}

	dij();

	for(int i=1;i<=m;i++){

		for(int j=0;j<E[i].size();j++){

			int x=E[i][j].first,t=E[i][j].sec,flag=1;

			if((!j)||dis[E[i][j-1].fir]+E[i][j].sec!=dis[E[i][j].fir]){

				if(T&&e[T].size()==1){

					pos[e[T][0].first].pop_back();

					e[T][0].first=x;

					flag=0;

				}

				else T++,e[T].push_back(mp(x,0));

			}

			else e[T].push_back(mp(x,t));

			if(flag)s[T].push_back(0),_x[T].push_back(0),_y[T].push_back(0);

			pos[x].push_back(mp(T,e[T].size()-1));

			//e:线路(点/和前面的长度)

			//pos:点(线路,对应位置)

			//s,_x,_y:dp用数组

		}

	}

	for(ll i=1;i<=T;i++)

		for(ll j=1;j<e[i].size();j++)

			e[i][j].sec+=e[i][j-1].sec;

	for(ll i=1;i<=n;i++)p[i]=i;

	sort(p+1,p+1+n,cmp);

	for(ll _i=1;_i<=n;_i++){

		ll x=p[_i];

		for(ll _j=0;_j<pos[x].size();_j++)

			calc(x,pos[x][_j].fir,pos[x][_j].sec,s[pos[x][_j].fir],top[pos[x][_j].fir]);

		for(ll _j=0;_j<pos[x].size();_j++)

			add(x,pos[x][_j].fir,pos[x][_j].sec,s[pos[x][_j].fir],top[pos[x][_j].fir]);

		if(x==n)break;

	}

	printf("%lld %lld\n",dis[n],f[n]);

	return 0;

}

巴特西

Loj#2769-「ROI 2017 Day 1」前往大都会【最短路树,斜率优化】

正题

题目大意

解题思路

code

最新文章

热门文章