就没人发现这个证明错了吗，

假设终点第一次出队列时不是最优 
      则说明当前队列中存在点u
         有 d[估计]< d[真实]
      d[u] + f[u] <= d[u] + g[u] = d[队头终点]

应该是d[u] + f[u] <= d[u] + g[u] < d[队头终点]

大佬们，有个问题我一直没想明白，为什么这道题的A*函数，小根堆一定要存PIII，不能像八数码那道题一样，当前状态到起点的距离单独存，然后小根堆就存pair<估计距离+到起点的实际距离,当前状态编号>呢？

试了一下，把A*函数替换成下面的，样例能过，但是只能过4/7个测试点，而且现有的题解全是存PIII的，实在想不明白为什么下面这样写不行QAQ

int astar()
{

    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push(  { dist[ori] ,  ori  }  );
    while(!pq.empty())
    {
        auto t= pq.top();
        pq.pop();
        int cur=t.y,distance=steps[cur];        
        cnt[cur]++;
        if(cnt[des]==k) return distance;

        for(int i=h[cur];~i;i=nxt[i]){
            int nt=order[i];
            if(cnt[nt]<k) 
            {
                steps[nt]=distance+val[i];              //steps[i]表示i距离起点的距离
                pq.push( {steps[nt]+dist[nt],nt  }  );
            }

        }

    }

    return -1;
}

int astar()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({dist[S], S});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, dis = t.first - dist[ver];
        cnt[ver] ++ ;

        if(cnt[T] == K)    return dis;
        for(int i = h[ver];~i;i = ne[i])
        {
            int j = e[i];
            if(cnt[j] < K)
                heap.push({dis + w[i] + dist[j], j});
        }
    }

    return -1;
}

这是因为求的是第 k 短路，你说的适合最短路。如果你是单独存储，并不能保证 steps 是合适的值。比如可能第 i 次更新会覆盖可能后面路的值

请教下不是说无解情况astar会退化成普通bfs，为什么这题有无解情况(-1)还能用

无解退化成bfs是第一短路，这题的无解情况(-1)是针对第k短路不存在时，你没有完全明晰A的执行过程与它所针对的问题，你可以看一下楼主这个A的证明 就是证明的：终点第一次出队时，即：单看这个证明就是 第一短路(就是平常所说的最短路)

老实人万岁

为什么估价函数是取每个点到终点的最短距离?

这样我们可以优先走那些可以尽快搜到终点的路呀

请问这个估计函数作用是什么？

相当于在搜索的过程在做贪心的选择

%%%

if(cnt[j] < K)的意思是终点最多被访问k次 所以中间的点也最多被访问k次吗？但是y总在视频里说中间的点可以被访问多次 有没有可能访问多余k次？

你搞懂了吗 我也在想这个问题

如果有这句话可以避免tle(因为可能到底不了cnt[ed]就一直为0) 因为从st到ed可能有无法到达的情况 你可以在dijkstra()函数之后 astar()函数之前加一个if(dis[st]==0x3f3f3f3f){puts(“-1”);return 0;}的话就可以ac了

如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,说明从j出发找不到第k短路(让终点出队k次)，即继续让j入队的话依然无解，那么就没必要让j继续入队了

如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,说明从j出发找不到第k短路(让终点出队k次)，即继续让j入队的话依然无解，那么就没必要让j继续入队了

%%%感谢你

我觉得你说得对 ；可以按照 ture_6 同学说的 弄一下，属于不连通的情况；仅存老实人 同学说的我感觉不对，只是数据比较弱，刚好这样判断能过了

这个解释有问题的吧，假设存在一条A到B的路径和一条B到A的路径边权都是1 并且A到C(C是终点)的路径是10*k 那么按照出队顺序 A和B即使出队k次之后依然是有解的 正确的解释应该是如果当前点出队超过k次的话 用它当前权值更新的其他点必然也是大于第k次的点 所以不需要更新

终于明白了，兄弟解释得真好

此处代码有两种写法：
1. 网上大神写法：

for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (cnt[v] < K)
                q.push({v, d + w[i], d + w[i] + dist[v]});
        }

1. 我的写法：

  for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (dist[v] < INF)                             // 如果是无效借力点，跳过
                q.push({v, d + w[i], d + w[i] + dist[v]}); // 点，距离，估值函数值
        }

原因：见$AcWing$给出错误时的数据用例：

#### 感悟
① 自我认为我的办法才是正解，因为你想把估值函数入队列，还指望着函数值小的优先，那如果d + w[i] + dist[v]>=INF，再往里放就是无效操作，而dist[v]是有可能等于INF的，因为
$$\large S->v-\ngtr T$$
此时，$v$就是 一个无效转移点，不用入队列，一次都不用！
② 通过错误的 数据用例 来反思、推导，加深理解非常重要,此处给$AcWing$满分，比某谷要强的多！与学会自我创造测试用例一样有用，在以后的学习中一次要重视起来。

感觉您说的有些问题，按照您的样例，最短路到k短路依次是a经过0,1,2,3……k次b再走到c，所以A和B出队超过k次之后必然是没有解的，而如果当前点出队超过k次， 用它当前权值更新的其他点也不一定超过k次，因为这个点的出度不一定是一。只有它的初度为一时，您的解释才是合法的

感觉if(cnt[j] < K)不应该出现在这里的，因为A里面不保证每个点访问第k次都是第k短路，只保证终点的每次访问，可以想一下K=1，最短路的情况，假设N=5,有五条边为
1 2 1
1 3 30
2 4 1
3 4 1
4 5 10000，起点为1，重点为5，估值为f[1…5]={0,999,1,1,0},满足A的要求，但是点4第二次访问才是最小值，因为估值函数让4在较差路径上提前被访问了

顶

dalao留批 /doge （尽管我还是没怎么会…）