Poj2387 spfa算法初识

题目大意十分简单，就是给你m条边的距离，让你求从1到n的最短路径.

解题思路：这是我第一次用spfa算法解题，学习spfa算法的心得都在代码注释里，若理解不对还请大牛们指出，谢谢啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define inf 1<<29
typedef struct Node
{
    int c;
    int u;
    int v;
};
Node nodes[4005];
int head[1005],next[4005],dist[1005];
bool visited[1005];
int num[1005];//用来判断是否存在负环，如果一个顶点入队超过n的话就说明有负环
int n,m;
int a1,a2,a3,e,sum;
void add_node(int u,int v,int c)
{
    nodes[e].u=u;
    nodes[e].v=v;
    nodes[e].c=c;
    next[e]=head[u];    //在这里可以解释为什么spfa算法可以避免重边
    head[u]=e;          //因为这里是将节点插入到起始节点之前，若有重边，则会查到原来已经插入的节点的前面
    e++;
}
bool relax(int u,int v,int c)
{
    if(dist[v]>dist[u]+c)
    {
        dist[v]=dist[u]+c;
        return true;
    }
    return false;
}
bool spfa()
{

    queue<int>que;
    for(int i=2;i<=n;i++)
    {
        dist[i]=inf;
    }
    dist[1]=0;visited[1]=true;
    que.push(1);
    while(!que.empty())
    {
        int q=que.front();
        que.pop();
        visited[q]=false;
        for(int i=head[q];i+1;i=next[i])//从q的头结点开始不断地往该邻接表的下一节点进行遍历
        {
            //若节点有更新则入队并标记为true，因为最短路肯定是由上一个被更新的节点得来的
            if(relax(q,nodes[i].v,nodes[i].c)&&!visited[nodes[i].v])//注意这里一定要先松弛，在进行标记判断
            {//因为有可能这个点已经被松弛过并入队列了，但找到一个更好的点到该点的距离更短，那也需要进行松弛
                if(++num[nodes[i].v]>n) //说明存在负环
                    return false;
                que.push(nodes[i].v);//没有负环则入队列
                visited[nodes[i].v]=true;

            }
        }
    }
    return true;
}
int main()
{

    while(scanf("%d%d",&m,&n)!=EOF)
    {
        sum=0;
        e=1;
        memset(nodes,0,sizeof(nodes));
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(visited,false,sizeof(visited));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a1,&a2,&a3);
            add_node(a1,a2,a3);//因为是无向边，因此要加两次节点
            add_node(a2,a1,a3);
        }
        spfa();

        printf("%d\n",dist[n]);
    }
    return 0;
}