世界真的很大
今天考了字符串
没看空限被86M卡空间唉，下次一定注意了
草草地学了一下这个什么Astar算法，也不算是完全了解吧就找了这道题来做做
Astar好像听说在AI方面有很多运用，但是只是在竞赛中的话一般用做搜索的剪枝和顺序处理
这道题体现的是后者

看题先：

description：

BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K <= 100)条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经. 请帮助BESSIE找出这K条最短路经的长度.你的程序需要读入农场的地图, 一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i). 所有(X_i, Y_i, D_i)满足(1 <= Y_i < X_i; Y_i < X_i <= N, 1 <= D_i <= 1,000,000).

input：

• 第1行: 3个数: N, M, 和K

• 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.

output：

• 第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.如果多条路经有同样的长度,请注意将这些长度逐一列出.

注意是n是起点，1是终点，一开始搞错了然后过不了样例233
首先跑K遍SPFA肯定不现实，因为一来时间大，二来不好实现
考虑直接爆搜
这样可以把每一条路径都搜出来
如果我们在每一次搜索的时候都能去搜索“当前还没有走过的路径的最小值”，那搜K次岂不是最短路了？
那么问题转化成暴力搜索最短路
总不能把所有路径搜出来排个序吧？
那么就是说在搜索最短路的时候，需要一个“导向型”的方法以完成剪枝

这个就是所说的Astar算法的“估价函数”了
由Astar算法引入估价函数来完成最短路的搜索的优化，保证每一次搜索都是尽量往短的路走，然后搜索K次就是前K短路了

问题在于这里的“估价函数”从何而来？
Astar算法的“估价函数”一般都是一个比较值，一个估计值，估计的越准确，效率就越高
这里需要估计的是什么呢？自然就是还剩的距离了
在选择方向时，一个点还剩的距离远小，这条路就越短，显然
当然还需要考虑当前已经实际走过的距离
即是说：
f（i） = g（i）+h（i）
这里g是实际走过的值，h是还要走的最短距离
本来A*是一个很玄的东西就是因为估价函数的准度直接影响搜索效率和顺序，但是在这里不存在
因为估计的值我们是可以直接算出来的，即某个点到1的最短路
这个可以建立反图SPFA，Dij什么的预处理得到
这样估计值就进化成了准确值，我们的Astar搜索时就不会有半点偏差

如果不是很好理解的话就想像一下Astar搜索最短路时的情景吧
在选择点前进的时候，哪个点离1近就选哪个，这样走出来肯定是最短路啊
然后搜索到一次之后重新搜索的时候，也是选择次小的方案，因为最小的已经选过了，那么就会选择当前最小的重新搜索，自然是次小值
如此重复K次之后就是答案了

讲道理Astar其实就是一个剪枝，并不是什么单独的算法，更是一种思想一样的东西
所以说其用的就是一个普通的BFS而已
但当然有一点不同
对一个点处理的时候一定要在其在队首的时候处理，不能在入队之前处理
由于这道题要求了“前K小”的顺序，只有在经过f值估价排序后才能决定处理顺序，如果直接在搜索到的时候处理就会变成建边顺序，这个肯定不对

按f值优先选择只需要把队列换成堆或者优先队列就好了

完整代码：

#include<stdio.h>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long dnt;const int INF=0x3f3f3f3f;struct edge
{int v,last,w;
}ed[200010],ad[200010];struct cow
{int id;dnt g,h;friend bool operator > (const cow &a,const cow &b){return a.g+a.h > b.g+b.h;}
};priority_queue <cow, vector<cow>,greater<cow> > state;
queue <int> q;int n,m,K,num=0,mum=0,cnt=0;
int head[100010],hed[100010];
dnt dis[100010],far[100010],a[100010];
int se[100010],src[100010];cow Make(dnt g,dnt h,int id)
{cow tmp;tmp.g=g,tmp.h=h,tmp.id=id;return tmp;
}void add(int u,int v,int w)
{num++;ed[num].v=v;ed[num].w=w;ed[num].last=head[u];head[u]=num;
}void ade(int u,int v,int w)
{mum++;ad[mum].v=v;ad[mum].w=w;ad[mum].last=hed[u];hed[u]=mum;
}void SPFA(int S)
{memset(dis,INF,sizeof(dis));q.push(S),dis[S]=0,se[S]=1;while(!q.empty()){int u=q.front();q.pop(),se[u]=0;for(int i=hed[u];i;i=ad[i].last){int v=ad[i].v;if(dis[v]>dis[u]+ad[i].w){dis[v]=dis[u]+ad[i].w;if(!se[v]) se[v]=1,q.push(v);}}}
}void Astar(int S)
{state.push(Make(0,dis[S],S));while(!state.empty()){int u=state.top().id;dnt w=state.top().g;state.pop();if(u==1) a[++cnt]=w;if(cnt==K) return ;for(int i=head[u];i;i=ed[i].last){int v=ed[i].v;state.push(Make(w+ed[i].w,dis[v],v));}}
}int main()
{scanf("%d%d%d",&n,&m,&K);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w),ade(v,u,w);}SPFA(1);memset(a,-1,sizeof(a));Astar(n);for(int i=1;i<=K;i++)printf("%lld\n",a[i]);return 0;
}
/*
EL PSY CONGROO
*/

嗯，就是这样