P14019 题解

· · 题解

容易想到把车站作为点建图跑最短路。

关键在于转车怎么处理，直接连边肯定是不行的：对于一个车站 x，已知 1 到它的距离 d_x 以及转车系数 b_x，则转车到 y 的代价为 b_xa_y+d_x，容易发现这是一个一次函数，关于 a_y 递增。

所以在同一个地方通过“转车”来转移时，一定是 a_y 较小的 y 先转移，并且转移的过程是取若干一次函数（该地点每个已经求出距离的车站都对应一个一次函数）的最小值。

因此在每个地点把对车站按 a 从小到大排序，用李超树维护一次函数最小值。每次求出一个车站的距离后更新李超树，对于它所在地点找到 a_y 最小的车站 y，求出 y 对应的最小值放进堆里即可。

时间复杂度是一只 \log。代码里面的 a,b 是反过来的。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
int n,m;
int a[200005], b[200005];

struct Node{
    int id,c,b;
    friend bool operator<(const Node &a,const Node &b){
        return a.b<b.b;
    }
};
vector<Node> zq[200005]; int p[200005];
int pos[400005];

struct Edge{
    int v,c,op; ll w;
    friend bool operator<(const Edge &a,const Edge &b){
        return a.w>b.w;
    }
};
vector<Edge> ed[400005]; int T1;
priority_queue<Edge> q;

struct Line{
    ll k,b;
    inline ll Val(const ll &x){return k*x+b;}
};
const int maxB=1000000;
struct Segtree{
    #define ci const int
    #define ulr int &u,ci &lp,ci &rp
    #define ls lc[u]
    #define lc_ ls,lp,mid
    #define rs rc[u]
    #define rc_ rs,mid+1,rp
    #define Chl if (Li.Val(lp)<li[u].Val(lp))
    #define Chr if (Li.Val(rp)<li[u].Val(rp))
    #define dmid int mid=lp+(rp-lp)/2
    Line li[600005];
    int lc[600005], rc[600005];
    int Rt[200005], T1;
    void modify(ulr,Line Li){
        if (!u) return li[u=++T1]=Li, void();
        dmid; if (li[u].Val(mid)>Li.Val(mid)) swap(li[u], Li);
        Chl modify(lc_,Li); Chr modify(rc_,Li);
        return ;
    }
    ll query(ulr,ci &p){
        if (!u) return inf;
        dmid; if (p<=mid) return min(query(lc_,p),li[u].Val(p));
        return min(query(rc_,p),li[u].Val(p));
    }
}Tr1;

ll dis[400005];
ll ddis[200005];

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d",b+i);
    for (int i=1;i<=m;i++) scanf("%d",a+i);
    for (int i=1;i<=m;i++){
        int d, s; scanf("%d %d",&d, &s);
        zq[s].push_back((Node){++T1,i,b[i]}); pos[T1]=s; s=T1;
        for (int j=2;j<=d;j++){
            int w,v; scanf("%d %d",&w,&v);
            zq[v].push_back((Node){++T1,i,b[i]});
            ed[s].push_back((Edge){T1,i,0,w}); pos[T1]=v; s=T1;
        }
    }
    for (int i=1;i<=n;i++) sort(zq[i].begin(), zq[i].end());
    memset(dis,0x3f,sizeof(dis)); memset(ddis,0x3f,sizeof(ddis)); 
    for (auto Nd:zq[1]) q.push((Edge){Nd.id,Nd.c,0,0});
    while (!q.empty()){
        auto Edd=q.top(); q.pop();
        int u=Edd.v, c=Edd.c, op=Edd.op; ll w=Edd.w; 
        if (dis[u]!=inf||w==inf) continue;
        int po=pos[u]; ddis[po]=min(ddis[po],w); dis[u]=min(dis[u],w);
        for (auto Ed:ed[u]) q.push((Edge){Ed.v,c,0,w+Ed.w});

        while (p[po]<zq[po].size()&&dis[zq[po][p[po]].id]!=inf) p[po]++;
        if (p[po]==zq[po].size()) continue;
        Tr1.modify(Tr1.Rt[po],1,maxB,(Line){a[c],w});
        auto Nd=zq[po][p[po]]; 
        q.push((Edge){Nd.id,Nd.c,1, Tr1.query(Tr1.Rt[po],1,maxB,Nd.b)});
    }
    for (int i=2;i<=n;i++) printf("%lld ",ddis[i]);
    return 0;
}