SPFA的卓越之处就在于处理多点稀疏图，因为点太多的话，我们直接用矩阵来存图的话是存不下的。
所以当我们用邻接矩阵来存图的话，我们就可以用SPFA来解决这类问题，spfa就是优化版的bellman-ford算法。
当我们无法对于单源最短路进行更新的话，说明所有的从起点出发的路已经都是最优了，这时候，我们的广搜也就结束了，
我们的spfa也就结束了。
我们从起点开始进入，然后选择和起点相邻的点，看看能否通过起点来更新，从起点到其它点的距离，如果可以，我们就让这下一个点进入队列，然后标记它在队列里面，然后我们再从下一个点进入，去更新其它的最短路。
这就是spfa，其实和dijkstra算法的主要核心思想并没有什么区别，只不过，spfa 要尝试去更新每条路，而不是像dijkstra一样，每次都去循环选择。
至于我们每次都让一个点只进入队列一次，原因就是在于我们每次只是选择一些我们可以更新的点，用这个可以更新的点，去更新其它点。
假设a点是原点，我们接着就让b和c入队列，我们通过b去更新的时候，发现c已经在队列里面了，我们对d[c]进行更新，看是否通过b点可以跟新c点，如果可以，就进行更新，更新之后发现c已经在队列里面了，我们就不添加c进入队列。
我们用完b之后，开始使用c点。
当我们用c去更新d，这时候就发现，因为d[c]是更新过的，如果可以更新，说明走b 更短，我们就可以通过c考虑走d是否更短，如果d[c]没有更新，就说明走b不短，所以我们就直接走c进行更新d，看看是否更短。
这时候我们可以知道，即使我们在更新b的时候，即使将c加入队列，也只是一种浪费资源的操作，所以，我们就不把c再次加入队列了。
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100005;
const int INF = 0x7f7f7f7f;
vector<int> v1[maxn];
vector<int> v2[maxn];
int n, m, s, t;
int d[maxn],isque[maxn];
void spfa()
{
d[s] = 0;
queue<int> q;
q.push(s);
isque[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
isque[u] = 0;
for (int i = 0; i < v1[u].size();i++) {
int v = v1[u][i];
int len = v2[u][i];
if (d[v]>d[u]+len) {
d[v] = d[u] + len;
if (!isque[v]) {
q.push(v);
isque[v] = 0;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
int u, v, c;
for (int i = 0; i < m;i++) {
scanf("%d%d%d", &u, &v, &c);
v1[u].push_back(v);
v1[v].push_back(u);
v2[u].push_back(c);
v2[v].push_back(c);
}
memset(d, INF, sizeof(d));
memset(isque, 0, sizeof(isque));
spfa();
printf("%d
", d[t]);
return 0;
}