题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1975
sol ：k短路裸题
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int Mxn=5010; const int Mxm=200010; struct Node { double f,g; int pos; } Q[10*Mxm]; bool operator < (Node a,Node b) { return a.f<b.f; } queue <int> q; int n,m,ans,siz,vis[Mxn]; int tot,head[Mxn],nxt[Mxm],ver[Mxm]; int Tot,Head[Mxn],Nxt[Mxm],Ver[Mxm]; double e,dis[Mxn],val[Mxm],Val[Mxm]; void add(int x,int y,double z) { nxt[++tot]=head[x]; ver[tot]=y; val[tot]=z; head[x]=tot; } void Add(int x,int y,double z) { Nxt[++Tot]=Head[x]; Ver[tot]=y; Val[tot]=z; Head[x]=Tot; } void spfa() { memset(dis,0x7f,sizeof(dis)); dis[n]=0,vis[n]=1,q.push(n); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=Head[x];i;i=Nxt[i]) { int y=Ver[i]; if(dis[y]>dis[x]+Val[i]) { dis[y]=dis[x]+Val[i]; if(!vis[y]) q.push(y),vis[y]=1; } } vis[x]=0; } } void push(Node x) { int now=siz+1; Q[++siz]=x; while(now>1) { if(Q[now>>1]<Q[now]) break; swap(Q[now],Q[now>>1]); now>>=1; } } Node pop() { int now=1,Next; Node tmp=Q[1]; Q[1]=Q[siz--]; while((now<<1)<=siz) { Next=now<<1; if(Next<siz&&Q[Next+1]<Q[Next]) Next++; if(Q[now]<Q[Next]) break; swap(Q[now],Q[Next]); now=Next; } return tmp; } void Astar() { Node a={dis[1],0,1}; push(a); while(siz) { Node now=pop(); int x=now.pos; for(int i=head[x];i;i=nxt[i]) { int y=ver[i];double g=now.g; Node b={g+val[i]+dis[y],g+val[i],y}; push(b); } if(x==n) { e-=now.f; if(e<0) return; ans++; } } } int main() { scanf("%d%d%lf",&n,&m,&e); for(int i=1,x,y;i<=m;i++) { double z; scanf("%d%d%lf",&x,&y,&z); add(x,y,z),Add(y,x,z); } spfa(); Astar(); printf("%d\n",ans); return 0; }