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

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&#p().x;double g&#p().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("%dn",ans);return 0;
}