本文共 1896 字，大约阅读时间需要 6 分钟。

题意就是求第k短路。。

先提醒一下一下不读题的朋友，起点是n，终点是1 特地找的这道题来做 至于怎么找，就是A* 不会A*的朋友不要慌，因为我也不会。。 定义看看就好

f(n)=g(n)+h(n)

f就是估价函数

正确性显然，主要是怎么弄出后面两个 我们从n点出发，当到达i点时 g值就是现在的路程 h值就是他最少还要多少距离才能到终点 当然，我也有疑惑，这个h有什么用啊！ 其实你只要想一下，你现在走的远，不一定就不优 但要是我们加上h的话，就知道你现在最好最好的情况要多少了

举个例子：

现在你到了2和3，代价分别是10和100，到1的距离是10000和1000 那你是用2更新更小的答案吗？当然不是！ 因为他下一步的代价很大

可能讲得不大清楚，看看代码画画图就好了。。

怎么实现呢

h值可以用SPFA预处理 然后g值在第一次的时候跑就好了，用dij 时间复杂度$O(nk)$其实我觉得要套多一个$log$，因为要用有点队列维护

贴个板子吧：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        typedef long long LL;using namespace std;const LL N=1005;const LL M=10005;LL n,m,k;struct qq{LL x,y,z,last;}s[M],s1[M];LL num,last[N];LL num1,last1[N];void init (LL x,LL y,LL z){    num++;    s[num].x=x;s[num].y=y;s[num].z=z;    s[num].last=last[x];    last[x]=num;    swap(x,y);    num1++;    s1[num1].x=x;s1[num1].y=y;s1[num1].z=z;    s1[num1].last=last1[x];    last1[x]=num1;}LL h[N];//起点到这里的最短距离     准确点来说，是这里到起点的最短距离bool in[N];void SPFA (){    queue
        
          q; memset(in,false,sizeof(in)); memset(h,127,sizeof(h)); q.push(1);in[1]=true;h[1]=0; while (!q.empty()) { LL x=q.front();q.pop(); for (LL u=last1[x];u!=-1;u=s1[u].last) { LL y=s1[u].y; if (h[y]>h[x]+s1[u].z) { h[y]=h[x]+s1[u].z; if (in[y]==false) { in[y]=true; q.push(y); } } } in[x]=false; } return ;}struct qt{ LL g,h,x; bool operator < (qt a) const { return a.g+a.h
         
           q; qt a,b; a.x=n;a.g=0;a.h=h[n];q.push(a); LL size=0; while (!q.empty()) { a=q.top();q.pop(); // printf("%lld %lld\n",a.x,a.g); cnt[a.x]++; if (cnt[a.x]>k) continue; if (a.x==1) ans[++size]=a.g; if (cnt[1]>=k) return ; for (LL u=last[a.x];u!=-1;u=s[u].last) { LL y=s[u].y; b.x=y; b.g=a.g+s[u].z; b.h=h[y]; q.push(b); } } return ;}int main(){ num=0;memset(last,-1,sizeof(last)); num1=0;memset(last1,-1,sizeof(last1)); scanf("%lld%lld%lld",&n,&m,&k); for (LL u=1;u<=m;u++) { LL x,y,z; scanf("%lld%lld%lld",&x,&y,&z); if (x