bzoj1975 [Sdoi2010]魔法猪学院（K短路，A*算法）

裸的K短路。听说内存会炸。。。反正bzoj上过了qaq
一个小剪枝：如果新扩展的点的路径总长度已经大于E了就不扩展了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 5010
#define M 200010
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,h[N],h1[N],num=0,ans=0;
double E,w[M],dis[N];bool inq[N];
struct edge{
    int to,next;
}data[M],data1[M];
struct node{
    int x;double g;
    node(int _x,double _g){x=_x;g=_g;}
    friend bool operator<(node a,node b){return a.g+dis[a.x]>b.g+dis[b.x];}
};
inline void A_star(){
    priority_queue<node>q;
    q.push(node(1,0));
    while(!q.empty()){
        int x=q.top().x;double g=q.top().g;q.pop();
        if(x==n){
            E-=g;if(E<0) return;++ans;continue;
        }for(int i=h[x];i;i=data[i].next){
            int y=data[i].to;if(g+w[i]+dis[y]>E) continue;
            q.push(node(y,g+w[i]));
        }
    }
}
inline void spfa(){
    queue<int>q;memset(dis,127,sizeof(dis));
    q.push(n);dis[n]=0;inq[n]=1;
    while(!q.empty()){
        int x=q.front();q.pop();inq[x]=0;
        for(int i=h1[x];i;i=data1[i].next){
            int y=data1[i].to;
            if(dis[x]+w[i]<dis[y]){
                dis[y]=dis[x]+w[i];if(!inq[y]) q.push(y),inq[y]=1;
            }
        }
    }
}
int main(){
// freopen("a.in","r",stdin);
    n=read();m=read();scanf("%lf",&E);
    while(m--){
        int x=read(),y=read();scanf("%lf",&w[++num]);
        data[num].to=y;data[num].next=h[x];h[x]=num;
        data1[num].to=x;data1[num].next=h1[y];h1[y]=num;
    }spfa();A_star();
    printf("%d\n",ans);
    return 0;
}