记录编号	470407	评测结果	AAAAAAAWWW
题目名称	[USACO Feb07] 奶牛聚会	最终得分	70
用户昵称	ユッキー	是否通过	未通过
代码语言	C++	运行时间	0.199 s
提交时间	2017-11-04 16:53:44	内存使用	1.49 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#define N 1100
#include <iostream>
using namespace std;
int head[N],nex[N],u[100001],v[100001],w[100001],dis[N];
bool vis[N];
int ans[N];
queue<int>Q;
int a[N<<1];
int h,t;
int n,m,x;
int maxx=0;
inline int read()
{
    int ret=0;
    char ch=getchar();
    while(ch>'9' || ch<'0')ch=getchar();
    while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
void SPFA(int s)
{
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    int i,tmp;
    vis[s]=1;
    dis[s]=0;
    Q.push(s);
    while(Q.size()!=0)
    {
        tmp=Q.front();
        Q.pop();
        vis[tmp]=0;
        for(i=head[tmp];i;i=nex[i])
        {
            if(dis[v[i]]>dis[tmp]+w[i])
            {
                dis[v[i]]=dis[tmp]+w[i];
                if(!vis[v[i]])
                {
                    Q.push(v[i]);
                    vis[v[i]]=1;
                }
            }
        }
    }
    ans[s]=dis[x];
}
int main()
{
    int i;
    freopen("sparty.in","r",stdin);
    freopen("sparty.out","w",stdout);
    n=read();m=read();x=read();
    for(i=1;i<=m;i++)
    {
        u[i]=read();v[i]=read();w[i]=read();
        nex[i]=head[u[i]];
        head[u[i]]=i;
    }
    for(i=1;i<=n;i++)
    {
        if(x!=n)SPFA(i);
    }
    SPFA(x);
    for(i=1;i<=n;i++){maxx=max(maxx,dis[i]+ans[i]);}
    printf("%d",maxx);
    return 0;
}