题解：P7984 [USACO21DEC] Tickets P

P7984 [USACO21DEC] Tickets P

思路

把每张票都看作一个节点，能买到票的检查站 c_i 向票连权值为 p_i 的边，票向能到达的检查站 [a_i,b_i] 连权值为 0 的边。

现在统计答案，需要求对于每个节点 i 的最短路 dis_{1,i} 和 dis_{i,n}，我们可以建反边分别跑以 1 和 n 为起点的最短路。

然后考虑如何合并答案。由于路径上重复经过的边只会累加一次代价，所以此时 dis_{1,i}+dis_{i,n} 并不是最终答案，因为可能存在重复计算了代价的边。

令 g_i 表示点 i 的最终答案，则 g_i\le dis_{1,i}+dis_{i,n}。
设 S_i 为点 i 答案中重复统计了的点的点集。
当 S_i=\varnothing 时，g_i=dis_{1,i}+dis_{i,n}。
当 S_i\ne\varnothing 时，总存在 u\in S_i 使得 S_u=\varnothing，此时 g_u=dis_{1,u}+dis_{u,n}。对于边 u\to v，当确定了 g_u 后，g_v=\min(g_v,g_u+w_{u\to v})。
我们发现这个转移和最短路的转移一模一样。
所以我们初始时假设每个点都没有重复计算的代价，令 g_i=dis_{1,i}+dis_{i,n}，最后再跑一遍最短路求 g。

由于要对连续的区间连边，所以用 DS 优化建图。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){//快读
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
const int N = 1e5+10,LG = 17;
const ll INF = 1e17;
int n,m;
struct{
    int to,nex; ll w;
}edge[N*LG*2];
int head[N*LG*2],edge_num;
inline void add(int x,int y,ll w){
    edge[++edge_num].to = y;
    edge[edge_num].nex = head[x];
    head[x] = edge_num;
    edge[edge_num].w = w;
}
int P=1,DEP=0,NOW;
ll dis[N*4],tmp[N*4];bool vis[N*4];
struct node{
    ll w; int p;
    bool operator < (const node&G) const{
        return w > G.w;
    }
};
priority_queue <node> q;
inline void dijkstra(){//最短路
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        node now = q.top();
        q.pop();
        vis[now.p] = 1;
        for(int i=head[now.p];i;i=edge[i].nex){
            int tto = edge[i].to;
            if(dis[tto]>dis[now.p]+edge[i].w){
                dis[tto] = dis[now.p]+edge[i].w;
                if(!vis[tto]) q.push({dis[tto],tto});
            }
        }
    }
}
int main(){
//  freopen("in.in","r",stdin);
//  freopen("out.out","w",stdout);

    read(n,m);//注意都建成反边
    while(P<=n+1) P<<=1,++DEP; NOW = (P<<1)-1;//zkw 优化建图
    for(int i=P-1;i;--i) add(i<<1,i,0),add(i<<1|1,i,0);
    for(int i=1,v,k,l,r;i<=m;++i){
        read(v,k,l,r);
        add(++NOW,v+P,1ll*k);//检查站向票的边
        // update
        l += P-1; r += P+1;
        while(l^1^r){
            if(~l&1) add(l^1,NOW,0);//票向检查站的边
            if(r&1) add(r^1,NOW,0);
            l>>=1;r>>=1;
        }
    }
    //1为起点的最短路
    for(int i=1;i<=NOW;++i) dis[i] = INF;
    dis[1+P] = 0; q.push({0,1+P}); dijkstra();
    //n为起点的最短路
    for(int i=1;i<=NOW;++i) tmp[i] = dis[i],dis[i] = INF;
    dis[n+P] = 0; q.push({0,n+P}); dijkstra();
    //再跑一遍最短路求最终答案
    for(int i=1;i<=NOW;++i){
        dis[i] += tmp[i];
        q.push({dis[i],i});
    }
    dijkstra();
    for(int i=1;i<=n;++i) printf("%lld\n",(dis[i+P]<INF)?dis[i+P]:-1);

//  fclose(stdin);
//  fclose(stdout);
    return 0;
}