记录编号	222975	评测结果	AAAAAAAAAA
题目名称	卡赞群岛	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.406 s
提交时间	2016-02-06 00:23:22	内存使用	4.17 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#define N 20010
#define M 200010
using namespace std;
ifstream in("kezan.in");
ofstream out("kezan.out");
int n,m;
vector<int> G[N],C[N],F[N],B[N];
bool l[N]={0},vis[N]={0};
int dfn[N]={0},low[N]={0};
int tim=0;
int s[N]={0},top=0;
int color[N]={0};
int col=0;
int f[N]={0},st[N]={0},en[N]={0},INF;
int start,end;
int q[N]={0};
class edge
{
public:
	int u,v,w;
	void make(int a,int b,int c)
	{
		u=a;
		v=b;
		w=c;
	}
	void print()
	{
		out<<u<<' '<<v<<' '<<w<<endl;
	}
}e[M];
void add1(int u,int v,int w)
{
	G[u].push_back(v);
	G[v].push_back(u);
	C[u].push_back(w);
	C[v].push_back(w);
}
void add2(int u,int v,int w)
{
	F[u].push_back(v);
	F[v].push_back(u);
	B[u].push_back(w);
	B[v].push_back(w);
}
void tarjan(int u,int fa)//求双联通分量
{
	int i,v,w;
	dfn[u]=low[u]=++tim;
	s[++top]=u;
	l[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(v!=fa)
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(l[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		col++;
		do
		{
			v=s[top];
			l[v]=0;
			color[v]=col;
			top--;
		}while(u!=v);
	}
}
void BFS(int s)//求直径的两个端点，则最长链为max(s[i],t[i])
{
	int i,u,v,w,l,r;
	l=r=1;
	for(i=1;i<=n;i++)
	{
		vis[i]=0;
		f[i]=INF;
	}
	q[++r]=s;
	f[s]=0;
	while(l<=r)
	{
		u=q[l];
		l++;
		vis[u]=1;
		for(i=0;i<F[u].size();i++)
		{
			v=F[u][i];
			w=B[u][i];
			if(!vis[v])
			{
				f[v]=f[u]+w;
				q[++r]=v;
			}
		}
	}
}
void read()
{
	int i,u,v,w;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>u>>v>>w;
		e[i].make(u,v,w);
		add1(u,v,w);
	}
	for(i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
}
void work()
{
	int i,u,v,ans;
	int temp=0;
	for(i=1;i<=m;i++)
	{
		u=e[i].u;
		v=e[i].v;
		if(color[u]!=color[v])//不同的商业联盟建边
		{
			add2(color[u],color[v],e[i].w);
		}
	}
	BFS(1);//从1号开始，最长的f[]为直径的一个端点
	for(i=1;i<=n;i++)
	{
		if(f[i]>temp)
		{
			temp=f[i];
			start=i;
		}
	}
	BFS(start);//从直径的一个端点开始，最长的f[]为直径的另一个端点
	temp=0;
	for(i=1;i<=n;i++)
	{
		if(f[i]>temp)
		{
			temp=f[i];
			end=i;
		}
		st[i]=f[i];
	}
	BFS(end);
	for(i=1;i<=n;i++)en[i]=f[i];
	for(i=1;i<=n;i++)
	{
		ans=max(st[color[i]],en[color[i]]);//最长链一定为该点到直径两端点的最大值
		out<<ans<<endl;
	}
}
int main()
{
	read();
	work();
	return 0;
}