在搜索的过程中，使用一个估价函数对当前点进行评估，找到最好的状态进行搜索，直到找到目标。 估价函数F(x)=G(x)+H(x)，其中G(x)为实际代价，H(x)为启发函数，这就是启发式。并且启发函数要满足：H(x) priority_queue heap; heap.push({0,T});//从终点开始搜 memset(dist, 0x3f, sizeof dist); dist[T] = 0; while(heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.y; if(st[ver]) continue; st[ver] = true; for(int i=rh[ver];i!=-1;i=ne[i]) { int j = e[i]; if(dist[j]>dist[ver]+w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j],j}); } } } } int astar() { priority_queue heap;//小根堆 // 谁的d[u]+f[u]更小 谁先出队列 heap.push({dist[S], {0, S}}); cout//搜到了 return distance; } for(int i=h[ver];i!=-1;i=ne[i]) { int j = e[i]; // 按 真实值+估计值 = d[j]+f[j] = dist[S,t] + w[t][j] + dist[j,T] 堆排 // 真实值 distance+w[i] heap.push({distance+w[i]+dist[j],{distance+w[i],j}}); } } return -1; } int main() { cin >> m >> n; memset(h,-1,sizeof h); memset(rh,-1,sizeof rh); for(int i=0;i