TOJ 3481 Highway Construction / 树的直径+SPFA

首先求出树的直径 然后把直径上的点都放近队列 做一次SPFA 求出最短路 求出最短路的最长路径即可

树的直径就是树上最远2点的路径 在直径上建这条路可以是答案尽量小 然后就可以做最短路了

还是很弱 比赛看出是树的直径没敢写 这方面练得不够多吧

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100010;
struct node
{
	int to, w;
};
vector <node> G[maxn];
int dis[maxn];
bool vis[maxn];
int path[maxn];
int p, leaf, n;


void BFS(int s)
{
	memset(vis, 0, sizeof(vis));
	memset(dis, 0, sizeof(dis));
	memset(path, 0, sizeof(path));
	queue <int> Q;
	Q.push(s);
	vis[s] = true;
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		for(int i = 0; i < G[u].size(); i++)
		{
			node x = G[u][i];
			int v = x.to;
			if(vis[v])
				continue;
			vis[v] = true;
			dis[v] = dis[u] + x.w;
			path[v] = u;
			//printf("%d\n", dis[v]);
			if(leaf < dis[v])
			{
				p = v;
				leaf = dis[v];
			}
			Q.push(v);
		}
	}
}

void BFS2()
{
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x7f, sizeof(dis));
	queue <node> Q;
	while(p)
	{
		//vis[p] = true;	
		dis[p] = 0;
		Q.push((node){p, 0});
		p = path[p];
	}
	while(!Q.empty())
	{
		node u = Q.front();
		Q.pop();
		vis[u.to] = false;
		for(int i = 0; i < G[u.to].size(); i++)
		{
			node x = G[u.to][i];
			int v = x.to;
			if(dis[v] > dis[u.to] + x.w)
			{
				dis[v] = dis[u.to] + x.w;
				if(!vis[v])
				{
					Q.push((node){v, dis[v]});
					vis[v] = true;
				}
				//printf("%d\n", dis[v]);
			}
		}
		
	}
}

int main()
{
	while(scanf("%d", &n) && n)
	{
		for(int i = 1; i <= n; i++)
			G[i].clear();
		for(int i = 1; i < n; i++)
		{
			int u, v, w;
			scanf("%d %d %d", &u, &v, &w);
			G[u].push_back((node){v, w});
			G[v].push_back((node){u, w});
		}
		leaf = 0;
		BFS(1);
		leaf = 0;
		BFS(p);
		BFS2();
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			ans = max(ans, dis[i]);
			//printf("%d\n", dis[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

TOJ 3481 Highway Construction / 树的直径+SPFA,布布扣,bubuko.com

TOJ 3481 Highway Construction / 树的直径+SPFA

原文：http://blog.csdn.net/u011686226/article/details/21296691