题解 P7984 [USACO21DEC] Tickets P

· · 题解

题目难度：USACO P/省选

先想暴力做法。注意到一个人不会重复买票，所以我们可以把每种票看作虚拟节点，买票看作从 c_i 到 i 号票边权为 p_i 的边，同时 i 号票向区间 [a_i,b_i] 中的所有点连边权为 0 的边。题目希望求出每个点到达 1 和 n 所需的最小代价，不妨建反图以 1 和 n 为原点分别跑一遍最短路。

然而这样会喜提 WA 。因为仍然没有解决重复买票的问题，两条最短路的交集中的所有边被算了两遍。怎么解决？先记当前答案为 dis_i=d1_i+dn_i ，若节点 u 的两条最短路均经过它的邻居 v ，不难发现 dis_u=dis_v+w 。这和单源最短路的松弛本质相同，我们对答案数组重新跑一遍最短路即可。

时间复杂度：O(NK\log(NK))

下面提供两种优化的思路，第一种是考场第一眼看出的线段树优化建图，具体知识可以参考这个博客 DS优化建图 。

对区间中的每个点暴力连边是不好的！我们用线段树建图的方式连边，时间复杂度为 O(N\log^2 N) 。USACO评测机或洛谷开 O2 均可通过本题。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e6+5,M=7e6+5;
const ll inf=1e16;
int head[N],cnt;
struct Edge{
    int to,nxt,w;
}e[M];
inline void add(int u,int v,int w){e[++cnt]={v,head[u],w};head[u]=cnt;}
int n,q,s;
struct Node{int l,r;}t[N];
#define ls (p<<1)
#define rs (ls|1)
inline void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){//叶子节点与原图加边
        add(l+8*n,p,0);add(p+4*n,l+8*n,0);
        add(p,l+8*n,0);add(l+8*n,p+4*n,0);
        return;
    }
    //向儿子连边
    add(p,ls,0);add((ls)+4*n,p+4*n,0);
    add(p,rs,0);add((rs)+4*n,p+4*n,0);
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
inline void upd(int p,int L,int R,int u,int w){
    int l=t[p].l,r=t[p].r,mid=(l+r)>>1;
    if(l==L&&r==R){//当前节点覆盖区间
        add(p+4*n,u+8*n,w);
        return;
    }
    if(R<=mid)upd(ls,L,R,u,w);
    else if(L>mid)upd(rs,L,R,u,w);
    else{
        upd(ls,L,mid,u,w);upd(rs,mid+1,R,u,w);
    }
}
ll dis[N],d[N];
struct node{
    ll dis;int pos;
    bool operator <( const node &x )const{
        return x.dis < dis;
    }
};
bool vis[N];
priority_queue <node> pq;
inline void dijkstra(bool op=0){
    if(!op){
        memset(dis,0x3f,sizeof(dis));
        dis[s]=0;pq.push({0,s});
    }else{
        rep(i,1,9*n+q)pq.push({dis[i],i});
    }
    memset(vis,0,sizeof(vis));
    while(!pq.empty()){
        node tmp=pq.top();pq.pop();
        int x=tmp.pos;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                pq.push({dis[y],y});
            }
        }
    }
}
int main(){
    n=read(),q=read();
    build(1,1,n);
    rep(i,1,q){
        int a=read(),w=read(),b=read(),c=read();
        upd(1,b,c,i+n,0);
        add(9*n+i,a+8*n,w);
    }
    s=8*n+1;
    dijkstra();
    memcpy(d,dis,sizeof(d));
    //rep(i,1,n)cout<<dis[i+8*n]<<' ';
    s=9*n;
    dijkstra();
    rep(i,1,9*n+q)dis[i]+=d[i];
    dijkstra(1);
    rep(i,1,n){
        if(dis[i+8*n]>inf)puts("-1");
        else printf("%lld\n",dis[i+8*n]);
    }
    return 0;
}

如何优化？考虑 dijkstra 时实际上在做什么。原图中的节点会影响将它包含的票的虚拟节点，然后这个虚拟节点仅影响其所对应的一个原图节点 (i\to c_i) 。其次，我们知道堆优化 dijkstra 后每个票仅会被更新一次。于是并不需要建出图，在线段树上转移并且对更新完的区间打上标记就可以做到 O(N\log N) （代码咕咕咕）。

第二种做法来自 Benq 的题解。同样利用上面的性质，对所有票按左端点升序排列，注意到每个门票最多入队一次，建一棵势能线段树维护一段区间的所有票右端点的最大值即可。在每个票入队后打上标记，均摊分析可以得出复杂度为 O(N\log N) 。目前在洛谷上是最优解。

时间复杂度：O(N\log N)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
const ll inf = 1e18;
struct ticket{int c,p,a,b;};
bool cmp(ticket x,ticket y){return x.a<y.a;}
struct SegTree{
    int n,sz;
    vector <int> mx;
    vector <ticket> tickets;
#define ls (p<<1)
#define rs (ls|1)
    void pushup(int p){mx[p]=max(mx[ls],mx[rs]);}
    SegTree(vector <ticket> tickets) : tickets(tickets){//初始化
        n = 1;
        sz = sz(tickets);
        while(n < sz)n<<=1;
        mx.assign(2*n,0);
        rep(i,0,n-1){
            if(i < sz){
                mx[i+n] = tickets[i].b;
            }else mx[i+n] = -1;
        }
        per(i,n-1,1)pushup(i);
    }
    //找到所有可能转移的门票并移除
    void remove(vector <int> &v,int x,int p=1,int L=0,int R=-1){
        if(R==-1)R+=n;
        if(L>=sz||tickets[L].a>x||mx[p]<x)return;
        if(L==R){
            mx[p] = -1;
            v.pb(L);
            return;
        }
        int mid = (L+R)>>1;
        remove(v,x,ls,L,mid),remove(v,x,rs,mid+1,R);
        pushup(p);
    }
};
void Min(ll &a,const ll b){if(a>b)a=b;}
int main(){
    int n=read(),k=read();
    vector <ticket> tickets(k);
    for(auto &t: tickets){
        t.c=read()-1,t.p=read(),t.a=read()-1,t.b=read()-1;
    }
    sort(ALL(tickets),cmp);
    auto Dij = [&](vector<ll> &dis){//Dijkstra
        priority_queue <pair<ll,int>> pq;
        rep(i,0,k-1){
            Min(dis[tickets[i].c],dis[i+n]+tickets[i].p);
        }
        rep(i,0,n-1){
            if(dis[i]<inf)pq.push({-dis[i],i});
        }
        SegTree seg(tickets);
        while(!pq.empty()){
            pii x = pq.top();
            pq.pop();
            if(-x.fi>dis[x.se])continue;
            vector <int> vec;
            seg.remove(vec,x.se);//找到转移的门票
            for(int t : vec){
                if(dis[t+n] > dis[x.se]){
                    dis[t+n] = dis[x.se];
                    if(dis[tickets[t].c] > dis[x.se] + tickets[t].p){
                        dis[tickets[t].c] = dis[x.se] + tickets[t].p;
                        pq.push({-dis[tickets[t].c],tickets[t].c});
                    }
                }
            }
        }
    };
    //三次最短路
    vector <ll> L(n+k,inf),R(n+k,inf),dis(n+k);
    L[0]=0,R[n-1]=0;
    Dij(L),Dij(R);
    rep(i,0,n+k-1)dis[i] = L[i] + R[i];
    Dij(dis);
    rep(i,0,n-1){
        if(dis[i]<inf)printf("%lld\n",dis[i]);
        else puts("-1");
    }
    return 0;
}