为什么使用spfa
最短路算法：
1.dijkstra
2.floyd
3.spfa
本题是求单源最短路，而且存在负边，所以应该用spfa
spfa原理
若给定的图存在负权边，类似Dijkstra算法等算法便没有了用武之地，SPFA算法便派上用场了。简洁起见，约定加权有向图G不存在负权回路，即最短路径一定存在。用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。SPFA采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
spfa核心代码
// spfa
memset(d, 0x3f, sizeof(d));
d[1] = 0;
q.push(1);
f[1] = true;
while (!q.empty()) {
int u = q.front();
for (int i = pre[u]; i != 0; i = a[i].next) {
int v = a[i].to;
if (d[u] + a[i].len < d[v]) {
d[v] = d[u] + a[i].len;
if (!f[v]) {
q.push(v);
f[v] = true;
}
}
}
q.pop();
f[u] = false;
}