题目简叙:

寒假到了,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);
}

码风较丑陋,请多包涵