题解 P7984 [USACO21DEC] Tickets P

· · 题解

令 f_i 表示从 i 出发的答案，则 f_i=\min_{i\to j}(f_j+val(i\to j)) 。初始值 f_i=dis_{i,1}+dis_{i,n}。

注意到这就是一个最短路更新 dp 的形式，线段树优化建出反图后跑 dijkstra 即可。时间复杂度 O(n\log^2 n)。

代码如下：

//author:望远星
#include<bits/stdc++.h>
#define pii pair<ll,int>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define db double
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') fh=-1; ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*fh;}
inline void out(int *a,int l,int r){fo(i,l,r) printf("%d ",*(a+i));puts("");}

const int N=4e6+5;
const ll inf=1e17;
struct Edge{
    int to,next,val;
}e[N];
ll dis[N],a[N];
int vis[N],ti,tot,head[N],n,m,qwq;

struct Node{
    int l,r,lt=0,rt=0;
}tree[N];
int num,root;

void connect(int x,int y,int v){
    //printf("connect(%d,%d,%d)\n",x,y,v);
    e[++tot]=(Edge){y,head[x],v};
    head[x]=tot;
}

void dij(int s,int o){
    //printf("dij(%d)\n",s);
    priority_queue<pii> q;
    if(o){
        fo(i,1,num+qwq) dis[i]=inf;
        dis[s]=0;q.push(mk(0,s));       
    }else fo(i,1,num+qwq) dis[i]=a[i],q.push(mk(-dis[i],i));
    ++ti;
    while(!q.empty()){
        while(!q.empty()&&vis[q.top().se]==ti) q.pop();
        if(q.empty()) break;
        int x=q.top().se;q.pop();
        vis[x]=ti;
        for(int i=head[x];i;i=e[i].next){
            int p=e[i].to;
            if(dis[p]>dis[x]+e[i].val){
                dis[p]=dis[x]+e[i].val;
                q.push(mk(-dis[p],p));
            }
        }
    }
//  fo(i,1,n) cout<<dis[i]<<" ";puts("");
}
//线段树优化，建反图，先以 1 为源点跑最短路，再以 n 为源点跑最短路，然后把每个结点的初始 dis 赋为 (1,i)+(n,i)，全扔进堆里跑 dij 

#define ls(x) x<<1
#define rs(x) x<<1|1

int build(int l,int r){
    //printf("build(%d,%d)\n",l,r);
    if(l==r){
        tree[l].l=l,tree[l].r=r;
        return l;
    }
    int mid=l+r>>1;int x=++num;
    //printf("num=%d,[%d,%d]\n",num,l,r);
    tree[x].l=l,tree[x].r=r;
    tree[x].lt=build(l,mid);
    tree[x].rt=build(mid+1,r);
    connect(tree[x].lt,x,0);
    connect(tree[x].rt,x,0);
    return x;
}

void update(int x,int l,int r,int aim){
    //printf("update(%d,%d,%d,%d,%d)\n",x,l,r,aim,val);//system("Pause");
    if(tree[x].l>=l&&tree[x].r<=r){
        connect(x,aim,0);//建反边 
        return;
    }
    int mid=(tree[x].l+tree[x].r)>>1;//,lt=tree[x].lt,rt=tree[x].rt;
    if(l<=mid) update(tree[x].lt,l,r,aim);
    if(r>mid) update(tree[x].rt,l,r,aim);
}

signed main(){
    cin>>n>>m;num=n;
    root=build(1,n);
    fo(i,1,m){
        int c=read(),p=read(),l=read(),r=read();
        ++qwq;
        update(root,l,r,qwq+num);
        connect(qwq+num,c,p);
    }
    dij(1,1);fo(i,1,num+qwq) a[i]+=dis[i];
    dij(n,1);fo(i,1,num+qwq) a[i]+=dis[i];
    dij(0,0);
    fo(i,1,n){
        if(dis[i]<=inf/2) cout<<dis[i]<<'\n';
        else cout<<"-1\n";
    }
    return 0;
}
/*
7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6
-------------------------------------------------
-1
-1
-1
1111
10100
110100
-1
*/