题解 P2483 【【模板】k短路 / [SDOI2010]魔法猪学院】

· · 题解

题解区怎么被A*占领了啊

发一发比较有道理的可持久化可并堆做法

我们先求出反向的以t为根的最短路树。那么一条从s到t的路径就会经过若干非树边和树边，我们可以用非树边序列来表示一条路径。

我们用优先队列来存储当前拓展出的非树边序列，每次选出一条最小的，然后扩展。

扩展的方式是两种：第一种是我们在序列后加上一条边，第二种是我们把序列最后一个给换掉。

对于第一种，我们对于每个点维护一个从x到t的树边所连出去的非树边的堆，(u→v,w)的权值是−dis[u]+w+dis[v]，即选择这条边所需要多花费的代价。这个可以使用可持久化可并堆实现。

对于第二种，我们是要把将这个方案放入优先队列时的可并堆保留下来，去掉之前选择元素后的最小值，也就是把根删除,可以直接把根的两个儿子merge起来作为新的堆;

本菜鸡调了近乎2h才发现最短路挂了

应该每次找最小的点出来松弛,而不是每次松弛找最小值丢就队列

希望能各位能不要像我这样石乐志吧

#include<bits/stdc++.h>
using namespace std;

const int N=5010,M=200010;
struct edge{
    int x,y,nex;
    double c;
    bool op;
}now[2][M];
struct node{
    int ls,rs,dis,y;
    double t;
}tr[10000010];
struct point{
    int num;
    double sum;
    bool operator<(const point q)const{
        return sum>q.sum;
    }
}X,Y;
priority_queue<point> f;
edge*s;
int fir[2][N],l[2],n,m,T,rt[5005010],ans,dfn;
double dis[N],E;
bool tf[N],we[N];
int*first;
const double eps=1e-8;

void ins(int x,int y,double c,int&len){s[++len]=(edge){x,y,first[x],c,false};first[x]=len;}
void new_node(double c,int y){tr[++T].dis=1;tr[T].t=c;tr[T].y=y;}

int merge(int x,int y){
    if(!x || !y) return x+y;
    if(tr[x].t>=tr[y].t-eps) swap(x,y);
    int p=++T;tr[p]=tr[x];
    tr[p].rs=merge(tr[p].rs,y);
    if(tr[tr[p].rs].dis>tr[tr[p].ls].dis) swap(tr[p].ls,tr[p].rs);
    tr[p].dis=tr[tr[p].rs].dis+1;
    return p;
}

void dfs(int x){
    we[x]=true;
    if(x!=n) for(int i=fir[0][x];i!=0;i=now[0][i].nex) if(!now[0][i].op) 
        new_node(now[0][i].c-dis[x]+dis[now[0][i].y],now[0][i].y),rt[x]=merge(rt[x],T);
    for(int i=first[x];i!=0;i=s[i].nex) if(!we[s[i].y] && dis[s[i].y]==dis[x]+s[i].c)
        now[0][i].op=true,rt[s[i].y]=rt[x],dfs(s[i].y);
}

void Dijkstra(){
    for(int i=1;i<n;i++) dis[i]=2000000000000.0;
    dis[n]=0;
    first=fir[1],s=now[1];
    while(1){
        int x=0,pos=0;
        double mmin=2000000000000.0;
        for(int i=1;i<=n;i++) if(!tf[i] && dis[i]<mmin) mmin=dis[i],x=i;
        if(!x) break;tf[x]=true;
        for(int i=first[x];i!=0;i=s[i].nex) if(!tf[s[i].y] && dis[x]+s[i].c<dis[s[i].y])
            dis[s[i].y]=dis[x]+s[i].c;
    }
    dfs(n);
}

void solve(){
    f.push((point){0,0});tr[0].y=1;
    while(!f.empty()){
        X=f.top();f.pop();
        if(E<dis[1]+X.sum) break;
        ans++;E-=dis[1]+X.sum;Y=X;
        if(tr[rt[X.num]].y!=n) X.sum+=tr[rt[X.num=tr[rt[X.num]].y]].t,f.push(X);
        if(tr[rt[Y.num]].ls || tr[rt[Y.num]].rs){
            Y.sum-=tr[rt[Y.num]].t;rt[++dfn]=merge(tr[rt[Y.num]].ls,tr[rt[Y.num]].rs);
            Y.sum+=tr[rt[Y.num=dfn]].t;f.push(Y);
        }
    }
    printf("%d\n",ans);
}

int main(){
    scanf("%d %d %lf",&n,&m,&E);
    int x,y;double c;
    for(int i=1;i<=m;i++){
        scanf("%d %d %lf",&x,&y,&c);
        s=now[0],first=fir[0],ins(x,y,c,l[0]);
        s=now[1],first=fir[1],ins(y,x,c,l[1]);
    }
    Dijkstra();dfn=n;solve();
}