正題

題目鏈接:https://loj.ac/p/2769

---

題目大意

給出$n$個點$m$條地鐵線路，每條線路是一條路徑。

求$1$到$n$的最短路且在最短路徑的情況下相鄰換乘點的距離平方和最大。

$1\le n,m,\sum s_i\le 10^6$

---

解題思路

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

因為每條可以計算和的路徑一定是連續(xù)的一段，所以考慮將一條鐵路線去掉不在最短路樹上的邊后分出若干段來。

對于每一段上的轉(zhuǎn)移都是一個$f_x=max\{f_y+(d_x?d_y{)}^2\}$的形式，可以斜率優(yōu)化。

但是為了充分轉(zhuǎn)移，需要按照$dis$從小到大轉(zhuǎn)移。

棧啊什么的開$vector$就好了。

時間復(fù)雜度$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:點(線路,對應(yīng)位置)//s,_x,_y:dp用數(shù)組 }}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; }

總結(jié)

以上是生活随笔為你收集整理的Loj#2769-「ROI 2017 Day 1」前往大都会【最短路树,斜率优化】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。