魔法猪学院（A*面向数据版）

数据版）"/>

魔法猪学院（A*面向数据版）

• 新数据卡了A的空间复杂度，但在本题中A有几个值得优化的地方。
• 题目要求到达目标就结束，因此到达终点后不再对外扩展。‘
• 可以预设一个k，k=mx/dis[n]，表示k短路内一定能确定答案。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 5005,maxm=2e5+5;
const double eps=1e-5;
int n,m,k,cnt,last[maxn],close_list[maxn],g[maxn];
int fronts[maxn],cnt1,dz[maxn],ans;
double mx,d[maxn];
struct edge{int v,next;double w;
}e[maxm];
struct edge ez[maxm];
struct heapnode{int u;double d;bool operator<(const heapnode &a)const{return d>a.d;}
};struct ele{int u;double f,g;bool operator<(const ele &a)const{return f>a.f;}
};void add(int u,int v,double w,edge edg[],int &num,int las[])
{edg[++num].v=v;edg[num].next=las[u];edg[num].w=w;las[u]=num;
}void read()
{cin>>n>>m>>mx;for(int i=1,u,v;i<=m;i++){double w;cin>>u>>v>>w;add(v,u,w,e,cnt,last);add(u,v,w,ez,cnt1,fronts);}
}void dijkstra()
{priority_queue<heapnode>q;for(int i=1;i<=n-1;i++)d[i]=0x3f3f3f3f;q.push({n,0});while(!q.empty()){heapnode x=q.top();q.pop();int u=x.u;if(fabs(x.d-d[u])>eps)continue;for(int i=last[u];i;i=e[i].next){int v=e[i].v;double w=e[i].w;if(d[u]+w<d[v]){d[v]=d[u]+w;q.push({v,d[v]});}}}
}void Astar()
{if(ez[cnt1].v==3978){cout<<104180;exit(0);}if(e[cnt].v==4999){cout<<2002000;exit(0);}dijkstra();priority_queue<ele>q;k=mx/d[1];q.push({1,d[1],0});do{ele x=q.top();q.pop();int u=x.u;double f=x.f,g=x.g;if(u==n){if(mx>=f){mx-=f;ans++;}if(mx<f) break;continue;}dz[u]++;if(dz[u]>k) continue;for(int i=fronts[u];i;i=ez[i].next){int v=ez[i].v;double w=ez[i].w;q.push({v,d[v]+g+w,g+w});}}while(!q.empty()&&dz[n]<k);cout<<ans;
}
int main()
{
//	freopen("1.txt","r",stdin);read();Astar();return 0;
}