Bellman_Ford算法和SPFA算法

给定一张有向图，若对与图中的某一条边(x,y,z)，有dist[y] <= dist[x] + z 成立，则称该边满足三角不等式。若所有边都满足三角不等式，则dist数组就是所求最短路。
Bellman_Ford算法的基本流程：
1.扫描所有边(x,y,z)，若dist[y] > dist[x] + z,则用dist[y]更新。
2.重复所有步骤，真到没有更新操作发生。
实际上，SPFA算法在国际上统称为:”队列优化版的Bellman_Ford算法”。
SPFA算法的基本流程：
1.建立一个队列，最初队列中只含有起点1。
2.取出都节点x，扫描它的所有出边(x,y,z)，若dist[y] > dist[x] + z,则用dist[y]更新。同时，若y不在队列中，则把y入列。
3.重复上面步骤，直到队列为空为止。
即使图中存在长度为负的边，Bellman_Ford和SPFA算法也能够成功。

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
const int N = 1000010,M = 1000010;
int head[N],ver[N],edge[N],next[N],d[N];
int n,m,tot;
queue<int> q;
bool v[N];

void add(int x,int y,int z){
    ver[++tot] = y; edge[tot] = z; next[tot] = head[x]; head[x] = tot;
}

void spfa(){
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1] = 0; v[1] = 1;
    q.push(1);
    while(q.size()){
        int x = q.front();
        q.pop();
        v[x] = 0;
        for(int i=head[x];i;i=next[i]){
            int y = ver[i], z = edge[i];
            if(d[y]>d[x]+z){
                d[y] = d[x] +  z;
                if(!v[y]) q.push(y),v[y] = 1;
            }
        } 
    }
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin >>  x >> y >> z;
        add(x,y,z);
    }
    spfa();
    return 0;
}