Poj2679 spfa算法深度应用

题目大意：给你村庄和村庄之间的距离和费用，如果这个村庄的费用可以无限小就输出UNBOUND，如果这两个村庄之间没有路就输出VOID，否则则输出在满足最小费用下的最短路。

算法思路：判断村庄费用无限小其实就是判断在所给的两个村庄a,b之间是否存在负环，注意全图存在负环但这两个村庄之间不存在负环的情况要考虑啊！因此我们要判断一下如果存在任意一个入队次数>n的点与b连通，或者本身b的入队次数就>n就说明a与b之间存在负环，输出UNBOUND,如果dist[b]==INF就说明a到不了b就输出VOID，否则输出最小费用和最小距离即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
int n,m,a,b,e,num1,num2,num3,num4,num5;
int head[2005],next[10050],dist[2005],dist2[2005];
bool visited[2005];
char str[50];
int num[2005];
bool flag;
typedef struct Edge
{
    int u;
    int v;
    int c;
    int value;
};
Edge edges[10050];
void addNode(int u,int v,int c,int value)
{
    //注意见图的时候这里要进行判断，某个点的单链表中如果有多条边的话，我们只取费用最小的那一个点组成单链表
    if(head[u]!=-1&&value>edges[head[u]].value)
        return;
    if(head[u]!=-1&&value<edges[head[u]].value)
        head[u]=-1;
    edges[e].u=u;
    edges[e].v=v;
    edges[e].c=c;
    edges[e].value=value;
    next[e]=head[u];
    head[u]=e++;
}
bool relax(int u,int v,int c,int value)
{

    if(dist2[v]>dist2[u]+value||dist2[v]==dist2[u]+value&&dist[v]>dist[u]+c)
    {
        dist2[v]=dist2[u]+value;
        dist[v]=dist[u]+c;
        return true;
    }

    return false;
}

bool spfa(int src)
{
    memset(visited,false,sizeof(visited));
    memset(num,0,sizeof(num));
    for(int i=0;i<n;i++)
    {
        dist[i]=INF;
        dist2[i]=INF;
    }
    dist[src]=0;
    dist2[src]=0;
    queue<int>que;
    visited[src]=true;
    que.push(src);

    while(!que.empty())
    {
        int q=que.front();
        que.pop();
        visited[q]=false;
        for(int i=head[q];i+1;i=next[i])
        {
            if(relax(q,edges[i].v,edges[i].c,edges[i].value)&&!visited[edges[i].v])
            {
                if(++num[edges[i].v]>n)
                    return false;
                visited[edges[i].v]=true;
                que.push(edges[i].v);
            }
        }

    }
    return true;
}
void dfs(int x,int y)
{
    visited[x]=true;
    if(x==y)//如果存在num[x]>n的点与结束点相连接的话，就标记
    {
        flag=true;
        return;
    }
    for(int i=head[x];i+1;i=next[i])
    {
            if(!visited[edges[i].v])
            {
                dfs(edges[i].v,y);
            }
    }
}
int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&a,&b))
    {
        e=0;flag=false;
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(edges,0,sizeof(edges));
        for(int i=0; i<m; i++)
        {
            int sum=0;
            int nn=0;
            bool isfu=false;
            scanf("%s",str);
            sscanf(str,"(%d,%d,%d[%d]%d)",&num1,&num2,&num3,&num4,&num5);
            addNode(num1,num2,num4,num3);
            addNode(num2,num1,num4,num5);

        }


         bool ok=spfa(a);

        for(int i=0;i<n;i++)
        {
            if(num[i]>n)
            {
                  memset(visited,false,sizeof(visited));
                flag=false;
                dfs(i,b);
                if(flag)
                    break;

            }
        }

        if(dist[b]==INF)
        {
            printf("VOID\n");
        }
        else
        {
            if(ok)
                printf("%d %d\n",dist2[b],dist[b]);
            else
            {
                if(flag||num[b]>n)
                     printf("UNBOUND\n");
                else
                    printf("%d %d\n",dist2[b],dist[b]);
            }
        }


    }
}