题解：P10652 「ROI 2017 Day 1」前往大都会

· · 题解

第一问可以直接最短路，考虑只有最短路上的点能对第二问有影响，所以重构出最短路图，具体地，一条边 (x,y,w) 在最短路图上的充分条件是 dis_x+w=dis_y。

考虑原图上的一条链在新图内会被分割成不相干扰的几条路径，所以直接将这些路径看作不同路径重新编号，然后可以 \text{DP}，设 f_i 表示 i 的答案，则 i 能从所有经过 i 的路径上的不与 i 重合的，且 dis_j < dis_i 的点 j 转移而来，方程为 f_i=\min(f_j+(dis_i-dis_j)^2)。这个形式一眼斜率优化，考虑对于每个路径维护凸包，对于每个点记录经过它的路径，从这些凸包转移，考虑一个点会转移经过他的路径条数次，这个次数等于它出度的一半，总转移次数就是 m 级别的，所以 DP 部分的均摊复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
namespace Aurora{ void Main(); }
int main(){ return Aurora::Main(),0; }
namespace Aurora{
    #define int long long
    #define ll long long
    #define debug printf("debug\n")
    const int N=1e6+5;
    int n,m,l[N],Road_Cnt=0,id[N];
    ll dis[N];
    struct EDGE{ int to;ll c; };
    struct Road{ int u,v;ll c; };
    vector<Road>r[N],nr[N];
    vector<int>cov[N];
    namespace Dij{
        bool vis[N];
        struct node{
            int x; ll dis;
            friend bool operator < (node A,node B){
                return A.dis>B.dis;
            } 
        };
        vector<EDGE>G[N];
        void Dijkstra(){
            priority_queue<node>Q; Q.push({1,0});
            memset(dis,0x3f,sizeof(dis)); dis[1]=0;
            while(!Q.empty()){
                int now=Q.top().x; Q.pop();
                if(vis[now]) continue;
                vis[now]=1;
                for(auto tx:G[now]){
                    int to=tx.to;
                    if(dis[to]>dis[now]+tx.c){
                        dis[to]=dis[now]+tx.c;
                        if(!vis[to]) Q.push((node){to,dis[to]});
                    }
                }
            }
        }
    }
    namespace CalcDP{
        ll f[N];
        int top[N];
        vector<int>st[N];
        #define X(i) (dis[i])
        #define Y(i) (f[i]+dis[i]*dis[i])
        #define K(i) (2*dis[i])
        #define Exval(i) (dis[i]*dis[i])
        double slope(int i,int j){
            return 1.0*(Y(i)-Y(j))/(X(i)-X(j));
        }
        void DP(){
            for(int i=1;i<=n;i++){
                int now=id[i];
                for(auto pos:cov[now]){
                    // printf("ID:%d POS:%d\n",i,pos);
                    while(st[pos].size()>1&&slope(st[pos][st[pos].size()-2],st[pos][st[pos].size()-1])<=1.0*K(now)) st[pos].pop_back();
                    if(st[pos].size()){
                        int j=st[pos][st[pos].size()-1];
                        f[now]=max(f[now],Y(j)-K(now)*X(j)+Exval(now));
                    }
                }
                for(auto pos:cov[now]){
                    while(st[pos].size()>1&&slope(st[pos][st[pos].size()-2],st[pos][st[pos].size()-1])<=slope(st[pos][st[pos].size()-1],now)) st[pos].pop_back();
                    st[pos].push_back(now);
                }
            }
        }
    }
    bool cmp(int A,int B){
        return dis[A]<dis[B];
    }
    void Main(){
        // freopen("tower_sample4.in","r",stdin);
        scanf("%lld%lld",&n,&m);
        for(int i=1,lst;i<=m;i++){
            scanf("%lld%lld",&l[i],&lst);
            for(int j=1;j<=l[i];j++){
                int x;ll w;scanf("%lld%lld",&w,&x);
                Dij::G[lst].push_back((EDGE){x,w});
                r[i].push_back((Road){lst,x,w});
                lst=x;
            }
        }
        Dij::Dijkstra();
        printf("%lld ",dis[n]);
        for(int i=1;i<=m;i++){
            for(auto now:r[i]){
                if(dis[now.u]+now.c==dis[now.v]) nr[i].push_back(now);
            }
            r[i].clear();
        }
        // for(int i=1;i<=m;i++){
        //     cout<<"ID:"<<i<<"\n"<<"NUM:"<<nr[i].size()<<"\n";
        //     for(auto now:nr[i]) printf("%d %d %lld\n",now.u,now.v,now.c);
        // }
        for(int i=1;i<=m;i++){
            // cout<<nr[i].size()<<endl;
            int lst=0;
            for(int j=1;j<nr[i].size();j++){
                if(nr[i][j-1].v!=nr[i][j].u){
                    Road_Cnt++;
                    for(int k=lst;k<=j-1;k++){
                        r[Road_Cnt].push_back(nr[i][k]);
                        cov[nr[i][k].u].push_back(Road_Cnt);
                    }
                    cov[nr[i][j-1].v].push_back(Road_Cnt);
                    lst=j;
                }
            }
            if(nr[i].size()){
                Road_Cnt++;
                for(int k=lst;k<nr[i].size();k++){
                    r[Road_Cnt].push_back(nr[i][k]);
                    cov[nr[i][k].u].push_back(Road_Cnt);
                }
                cov[nr[i][nr[i].size()-1].v].push_back(Road_Cnt);
            }
        }
        // cout<<"RC:"<<cov[1][0]<<" "<<cov[2][0]<<endl;
        // for(int i=1;i<=n;i++){
        //     printf("dis[%d]:%lld\n",i,dis[i]);
        // }
        for(int i=1;i<=n;i++) id[i]=i;
        sort(id+1,id+n+1,cmp);
        CalcDP::DP();
        printf("%lld\n",CalcDP::f[n]);
    }
}