[POJ3268]Silver Cow Party[SPFA]

#include<cstdio>
#include<cstring>
#include<queue>
#define re register
#define in inline
using namespace std;
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    if(b)return -s;
    return s;
}
const int size=1005;
int n,m,x,head[size],cnt,dis1[size],dis2[size],b[size],eu[100005],ev[100005],ew[100005];
struct edge{int t,w,nxt;}e[100005];
in void add(int f,int t,int w){e[++cnt].t=t,e[cnt].w=w,e[cnt].nxt=head[f],head[f]=cnt;}
in void spfa(int dis[])
{
    memset(b,0,sizeof(b));
    queue<int> q;
    while(!q.empty()) q.pop();
    for(re int i=1;i<=n;++i) dis[i]=20000000;
    q.push(x);
    b[x]=1,dis[x]=0;
    while(!q.empty())
    {
	int u=q.front();q.pop();
	b[u]=0;
	for(re int i=head[u];i;i=e[i].nxt)
	{
	    int v=e[i].t;
	    if(dis[v]>dis[u]+e[i].w){
		dis[v]=dis[u]+e[i].w;
		if(!b[v]){b[v]=1;q.push(v);}
	    }
	}
    }
}
signed main()
{
    n=read(),m=read(),x=read();
    for(re int i=1;i<=m;++i)
    {
	eu[i]=read(),ev[i]=read(),ew[i]=read();
	add(eu[i],ev[i],ew[i]);
    }
    spfa(dis1);
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    cnt=0;
    for(re int i=1;i<=m;++i) add(ev[i],eu[i],ew[i]);
    spfa(dis2);
    int ans=0;
    for(re int i=1;i<=n;++i)
	if(dis1[i]+dis2[i]>ans) ans=dis1[i]+dis2[i];
    printf("%d\n",ans);
    return 0;
}