题目简叙：

寒假到了，N头牛都要去参加一场在编号为X（1≤X≤N）的牛的农场举行的派对（1≤N≤1000），农场之间有M（1≤M≤100000）条有向路，每条路长Ti（1≤Ti≤100）。

每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这N头牛的最短路径（一个来回）中最长的一条路径长度。

分析：

其实这道题的考点就是单元最短路径和单终点最短路径。

单终点最短路径其实就可以把所有的边反过来，直接就转换为单源最短路径了。

于是此题的核心就是跑两遍dijkstra或spfa了（本人偏好dijkstra）。

还有就是注意变量不要重复

代码：

#include<cstdio>

#include<queue>

#include<vector>

using namespace std;

struct edge

{

	int to,val;

};

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q,w;

vector<edge> e[1005],f[1005];

int n,m,s;

int dis[1005],his[1005],vis[1005],visit[1005];

void dijkstra_zheng()//正常的单元最短路，也就是牛们散伙时的最短路

{

	for(int i=1;i<=n;i++)

	{

		dis[i]=2147483647;

	}

	dis[s]=0;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		int x=q.top().second;

		q.pop();

		if(vis[x]==1)

		continue;

		vis[x]=1;

		for(int i=0;i<e[x].size();i++)

		{

			int y=e[x][i].to;

			if(dis[x]+e[x][i].val<dis[y])

			{

				dis[y]=dis[x]+e[x][i].val;

				q.push(make_pair(dis[y], y));

			}

		}

	}

}

void dijkstra_dao()//反过来的最短路，也就是牛们去开派对的最短路

{

	for(int i=1;i<=n;i++)

	{

		his[i]=2147483647;

	}

	his[s]=0;

	w.push(make_pair(0,s));

	while(!w.empty())

	{

		int x=w.top().second;

		w.pop();

		if(visit[x]==1)

		continue;

		visit[x]=1;

		for(int i=0;i<f[x].size();i++)

		{

			int y=f[x][i].to;

			if(his[x]+f[x][i].val<his[y])

			{

				his[y]=his[x]+f[x][i].val;

				w.push(make_pair(his[y], y));

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	for(int i=1;i<=m;i++)

	{

		int x,y,z;

		scanf("%d%d%d",&x,&y,&z);

		edge tmp;

		tmp.to=y;

		tmp.val=z;

		e[x].push_back(tmp);

		tmp.to=x;

		tmp.val=z;

		f[y].push_back(tmp);//倒着再存一遍

	}

	dijkstra_zheng();

	dijkstra_dao();

	int ans=0;

	for(int i=1;i<=n;i++)

	{

		if(his[i]+dis[i]>ans)

		{

			ans=his[i]+dis[i];

		}//求最大值就行了

	}

	printf("%d",ans);

}

码风较丑陋，请多包涵