@[Xing_ke](/user/247546) 您的解题方案存在四个错误。
（1）您的代码：
```
bool operator<(const node &x)const{
x.dis<dis;
}
```
未返回值，则函数默认返回false，导致无法对优先队列内的元素进行排序，应该更改为：
```
bool operator<(const node &x)const{
return x.dis<dis;
}
```
（2）您的代码：
```
for(int i=1;i<=n;++i) dis[i]=inf;
```
未将dis[n]初始化为0，则无法正确求得最短距离，应该更改为：
```
for(int i=1;i<=n;++i) dis[i]=inf;
dis[n] = 0;
```
（3）您的代码：
```
while(!Q.empty()){
```
应该是将q误写为Q了，q才是优先队列。应该更改为：
```
while(!q.empty()){
```
（4）A\*搜索未能正确应用。A\*搜索的核心在于使用g(x)和h(x)来估算得到代价函数f(x)，在本题环境下，g(x)相当于当前实际走的路程，h(x)则相当于距离顶点n的最短距离，该距离您已经使用SPFA算法计算得到，存放在数组dis中。阅读您的代码，结构体node中的数据域dis应该是总的代价函数f(x)，但是走到当前顶点的实际代价g(x)在哪里呢？似乎并未体现。因此需要将结构体适当修改：
```
struct node{
int id;
double gx, dis;
bool operator<(const node &x)const{
return x.dis<dis;
}
};
```
对应的，在搜索可能的路径时，需要将原代码：
```
pos.dis-=dis[x]; // 这是什么意思？我没有看懂。
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
double wc=e[i].val;
q.push((node){y,dis[y]+pos.dis+wc});
}
```
修改为（注意，初始压入的结点值需要在原有代码上做相应更改）：
```
q.push((node){1,0,0});
// ...
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
double wc=e[i].val;
q.push((node){y, pos.gx + wc, pos.gx + wc + dis[y]});
}
```
修改完毕后，我尝试提交了一下，有一个测试点MLE，其他测试点Accepted。
有空请您访问我的[CSDN博客](https://blog.csdn.net/metaphysis)，里面有我写的一本书，内有编程竞赛相关内容的介绍，并附有对应的练习题目（题目源自UVa OJ），可免费下载此书的PDF版本：[《C++，挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252)。可以的话，还烦您向对编程感兴趣的朋友推荐一下我的博客和书，感谢！
by metaphysis @ 2020-04-02 21:53:08
dalao~非常感谢！！！@[metaphysis](/user/333388)
能办的我会尽可能帮忙的，谢了>WQ
by Xing_ke @ 2020-04-02 22:12:26
>未返回值，则函数默认返回false
@[metaphysis](/user/333388) 这一句是错误的，无返回值时返回为EAX寄存器中的值，可能为任意值，并非默认$false$。
by gxy001 @ 2020-08-24 16:07:50
@[gxy001](/user/55707)
您说的是哪个地方，我没有看明白，您能再明确一些吗？
by metaphysis @ 2020-08-24 20:29:34
@[metaphysis](/user/333388) 您的这句话（“未返回值，则函数默认返回false”）是错误的，不存在默认返回值，返回值可能为任意值
by gxy001 @ 2020-08-24 22:02:03
@[gxy001](/user/55707)
感谢您的指正。
by metaphysis @ 2020-08-25 07:33:58