记录编号	297749	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-08-18 16:37:49	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int maxm=100005;
const int maxn=1005;
queue<int> q;
int u[maxm],v[maxm],w[maxm],next[maxm],next1[maxm],first[maxn],first1[maxn],d[maxn],maxx[maxn];
bool flag[maxn];
int cc()
{
	freopen("partyb.in","r",stdin);
	freopen("partyb.out","w",stdout);
	int i,n,m,k,x,ans=-1;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)
	  d[i]=0x7fffffff/2,first[i]=-1,first1[i]=-1;
	d[k]=0;
	for(i=1;i<=m;i++)
	  scanf("%d%d%d",&u[i],&v[i],&w[i]),next[i]=first[u[i]],first[u[i]]=i,next1[i]=first1[v[i]],first1[v[i]]=i;
	//=======================================================the first
	q.push(k);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		flag[x]=false;
		for(i=first[x];i!=-1;i=next[i])//x是有向边的头,邻接表存的是有向边的尾 
		  if(d[v[i]]>d[x]+w[i])
		  {
			d[v[i]]=d[x]+w[i];
			if(!flag[v[i]])
			  q.push(v[i]),flag[v[i]]=true;
		  }
	}
	for(i=1;i<=n;i++)
	  maxx[i]+=d[i];
	//=======================================================the second
	for(i=1;i<=n;i++)
	  d[i]=0x7fffffff/2,first[i]=-1;
	d[k]=0;
	q.push(k);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		flag[x]=false;
		for(i=first1[x];i!=-1;i=next1[i])//x是有向边的头,邻接表存的是有向边的尾 
		  if(d[u[i]]>d[x]+w[i])
		  {
			d[u[i]]=d[x]+w[i];
			if(!flag[u[i]])
			  q.push(u[i]),flag[u[i]]=true;
		  }
	}
	for(i=1;i<=n;i++)
	  maxx[i]+=d[i];
	for(i=1;i<=n;i++)
	  if(ans<maxx[i]&&maxx[i]<0x7fffffff/2)
	    ans=maxx[i];
	printf("%d\n",ans);
	return 0;
}
int ccc=cc();
int main(){;
}