BZOJ1975: [Sdoi2010]魔法猪学院（A*）

学院（A*）"/>

BZOJ1975: [Sdoi2010]魔法猪学院（A*）

传送门

题意：
求k短路。

题解：
标准A*，先从终点SPFA，保证估价函数的正确。

(感觉这个复杂度很不科学。。)

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,double> pid;
const int Maxn=5e3+50;
int n,m,cnt;
double E,dis[Maxn];;
vector< pid >edge[Maxn];
vector< pid >revedge[Maxn];
struct cmp_g{inline bool operator()(const pid &a,const pid &b){return a.second+dis[a.first]>b.second+dis[b.first];}
};
typedef __gnu_pbds::priority_queue<pid,cmp_g,pairing_heap_tag> heap;
heap q;
inline void SPFA(){static queue<int> que;static int exi[Maxn];for(int i=1;i<=n;i++)dis[i]=1e9;dis[n]=0;que.push(n);exi[n]=0;while(!que.empty()){int u=que.front();que.pop();exi[u]=0;for(int e=revedge[u].size()-1;e>=0;e--){int v=revedge[u][e].first;double w=revedge[u][e].second;if(dis[v]<dis[u]+w)continue;dis[v]=dis[u]+w;if(!exi[v])que.push(v),exi[v]=0;}}
}
inline void A_star(){q.push(make_pair(1,0));while(E>0){pid u=q.top();q.pop();if(u.first==n){E-=u.second;if(E>=0){++cnt;continue;}if(E<=0)break;}for(int e=edge[u.first].size()-1;e>=0;e--){int v=edge[u.first][e].first;double w=edge[u.first][e].second;q.push(make_pair(v,u.second+w));}}
}
int main(){scanf("%d%d%lf",&n,&m,&E);for(int i=1;i<=m;i++){int x,y;double e;scanf("%d%d%lf",&x,&y,&e);edge[x].push_back(make_pair(y,e));revedge[y].push_back(make_pair(x,e));}SPFA();A_star();printf("%d",cnt);
}