@[ffox](/user/332728)
阅读了您的代码，发现存在两处问题，一处是“致命性的”，一处是“非致命性的”，但存在隐患。
（1）您在代码中使用：
```
flag[a]=1;
flag[b]=1;
```
来标记Rome Road的路口，但是在后续建图时，使用：
```
if(flag[i]&&flag[j])
```
的方式来判断两个路口之间是否有Rome Road，这样是错误的。假设给定的图中路口1和路口5之间存在Rome Road，路口5和路口10之间存在Rome Road，但路口1和路口10之间不存在Rome Road。按照您的方式建图，flag[1]、flag[5]、flag[10]均为真，这样会凭空在路口1和路口10之间建立一条Rome Road，从而导致后续的最短距离计算大概率发生错误。
（2）在您的SPFA（Shortest Path Faster Algorithm）实现中：
```
void spfa(int s)
{
queue < int >q;
fill(d, d + maxn, INF);
d[s] = 0;
memset(vis, 0, sizeof(vis));
q.push(s);
// 在标准的SPFA中，应该将s标记为已访问。
// vis[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
// 此处按照标准的SPFA实现，应该是将u标记为未访问，即vis[u] = 0，
// 以便后续再次将u送入队列。不过由于本题是无向图的最短路径，
// 每个顶点只需进入队列一次即可，不会产生潜在的副作用，
// 但是在求不包含负权值圈的图的最短路径时，就可能存在问题，
// 因为您拒绝了u再次进入队列的可能性，而u是有可能再次进入队列的。
vis[u] = 1;
for (int i = 0; i < G[u].size(); i++)
{
Edge & e = edges[G[u][i]];
if (d[e.v] > d[u] + e.w)
{
d[e.v] = d[u] + e.w;
if (!vis[e.v])
{
vis[e.v] = 1;
q.push(e.v);
}
}
}
}
}
```
有空请您访问我的[CSDN博客](https://blog.csdn.net/metaphysis)，里面有我写的一本书，内有编程竞赛相关内容的介绍，并附有对应的练习题目（题目源自UVa OJ），可免费下载此书的PDF版本。[《C++，挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252)，感谢！
by metaphysis @ 2020-03-31 08:50:27
谢谢大佬！！！ac了
by ffox @ 2020-03-31 10:32:41