记录编号	58320	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2013-04-19 11:37:23	内存使用	3.31 MiB

#include<fstream>
#include<vector>
using namespace std;
ifstream fi("partyb.in");
ofstream fo("partyb.out");
const int infi=100000001;
int n,m,k,ans;
class adj
{
public:
	int vertex,weight;//边的另一个端点和权值
};
vector <adj> map1[1001],map2[1001];//原图与反向图
int time1[1001],time2[1001];//从k回家的时间与从某点到k的时间
bool boo[1001];
int main()
{
	fi>>n>>m>>k;
	int i,j,x,y,w;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y>>w;
		adj tmp;
		tmp.vertex=y;tmp.weight=w;
		map1[x].push_back(tmp);//原图
		tmp.vertex=x;
		map2[y].push_back(tmp);//反向图，这样所有到k的路径都变成了从k出发的路径
	}
	//==================================================================预处理完毕
	for(i=1;i<=n;i++)time1[i]=infi,boo[i]=false;
	time1[k]=0;
	for(i=1;i<=n-1;i++)
	{
		x=1;while(boo[x])x++;
		for(j=x+1;j<=n;j++)if(!boo[j]&&time1[j]<time1[x])x=j;
		boo[x]=true;
		y=map1[x].size();
		for(j=0;j<y;j++)
			if(!boo[map1[x][j].vertex]&&time1[map1[x][j].vertex]>time1[x]+map1[x][j].weight)
				time1[map1[x][j].vertex]=time1[x]+map1[x][j].weight;
	}
	//for(i=1;i<=n;i++)fo<<time1[i]<<' '<<endl;
	//原图中Dijstra
	for(i=1;i<=n;i++)time2[i]=infi,boo[i]=false;
	time2[k]=0;
	for(i=1;i<=n-1;i++)
	{
		x=1;while(boo[x])x++;
		for(j=x+1;j<=n;j++)if(!boo[j]&&time2[j]<time2[x])x=j;
		boo[x]=true;
		y=map2[x].size();
		for(j=0;j<y;j++)
			if(!boo[map2[x][j].vertex]&&time2[map2[x][j].vertex]>time2[x]+map2[x][j].weight)
				time2[map2[x][j].vertex]=time2[x]+map2[x][j].weight;
	}
	//for(i=1;i<=n;i++)fo<<time2[i]<<' '<<endl;
	//反向图中Dijstra
	ans=0;
	for(i=1;i<=n;i++)
		if(time1[i]!=infi&&time2[i]!=infi&&ans<time1[i]+time2[i])
			ans=time1[i]+time2[i];
	fo<<ans;
	return 0;
}