Poj3268 spfa算法应用

题目大意：来自n个农场的n头牛去一个给定的x农场吃草，来回都走最短路，这几个牛所走过的最大的路是多少。

算法思想：spfa的应用，对每头牛去的时候搞一次spfa,回来的时候在搞一次spfa，再将这两段距离之和相加。最后在维护一下最大值输出即可。

如果不大清楚spfa算法，可以参考下http://huyifan951124.iteye.com/blog/2315252

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF -0x3f3f3f3f
#define INF2 0x3f3f3f3f
int n, m, x;
int a,b,c,e,Max,flag,flag2;
typedef struct Edge
{
    int u;
    int v;
    int c;
};
Edge edges[200050];
int next[200050],head[1005],dist[1005];
bool visited[1005];
void addnode(int u,int v,int c)
{
    edges[e].u=u;
    edges[e].v=v;
    edges[e].c=c;
    next[e]=head[u];
    head[u]=e++;
}
bool relax(int u,int v,int c)
{
    if(dist[v]>dist[u]+c)
    {
        dist[v]=dist[u]+c;
        return true;
    }
    return false;
}
int spfa(int src,int x)
{
    memset(visited,false,sizeof(visited));

    for(int i=1;i<=n;i++)
    {
        dist[i]=INF2;
    }
    dist[src]=0;
    queue<int>que;
    que.push(src);
    visited[src]=true;
    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)&&!visited[edges[i].v])
            {
                visited[edges[i].v]=true;
                que.push(edges[i].v);
            }
        }
    }
    return dist[x];
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    scanf("%d%d%d",&n,&m,&x);

    e=1;Max=INF;

    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addnode(a,b,c);
    }
    for(int i=1;i<=n;i++)
    {
        flag=-1;
        if(i==x)
            continue;
        flag=spfa(i,x);
        flag2=spfa(x,i);
        if(Max<(flag2+flag))
            Max=flag2+flag;
    }

    printf("%d\n",Max);


    return 0;

}