Description

Input

Output

Sample Input

Sample Output

HINT

Source

由于最短路径只有一条，所以可以求出最短路径树。

那么我们随便加入一条非树边(u,v)，就会形成一个环：

加入红边之后，蓝色点的路径会被更新。

蓝色点其实就是环上除了lca(u,v)之外的所有点，那么他们被更新成什么了？

i点：dist[u]+dist[v]+E(u,v)-dist[i]

因此更新后的答案与uv这条边的k=dist[u]+dist[v]+E(u,v)是有关的，为了求出最短的，我们只要按照每条边的k值升序排序，依次更新即可。

已经更新过的点，再遇到时就不必更新了，我是用并查集水过的。。

正解应该是树链剖分，用线段树来做即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define M 100005
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
int h[M],d[M],now=0,tot=0,m,n,inq[M],ans[M],f[M],fa[M];
struct edge
{
	int x,y,ne,t;
}e[M*5],e1[M*5];
struct Edge
{
	int x,y,v;
}E[M*5];
void read(int &tmp)
{
	tmp=0;
	char ch=getchar();
	int fu=1;
	for (;ch<'0'||ch>'9';ch=getchar())
		if (ch=='-') fu=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())
		tmp=tmp*10+ch-'0';
	tmp*=fu;
}
void Addedge(int x,int y,int t)
{
	e[++tot].y=y;
	e[tot].ne=h[x];
	e[tot].t=t;
	h[x]=tot;
}
void spfa()
{
	for (int i=1;i<=n;i++)
		d[i]=inf,inq[i]=0;
	queue<int> q;
	q.push(1),inq[1]=1,fa[1]=0,d[1]=0;
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		inq[x]=0;
		for (int i=h[x];i;i=e[i].ne)
		{
			int y=e[i].y;
			if (d[y]>d[x]+e[i].t)
			{
				d[y]=d[x]+e[i].t;
				fa[y]=x;
				if (!inq[y]) q.push(y),inq[y]=1;
			}
		}
	}
}
bool cmp(Edge a,Edge b)
{
	return a.v<b.v;
}
int Getfather(int x)
{
	return f[x]==0?x:f[x]=Getfather(f[x]);
}
void Solve(int x,int y,int v)
{
	while (Getfather(x)!=Getfather(y))
	{
		int f1=Getfather(x),f2=Getfather(y);
		x=f1,y=f2;
		if (d[x]<d[y]) swap(x,y);
		ans[x]=v-d[x];
		now++;
		f[x]=fa[x];
		x=f[x];
	}
}
int main()
{
        read(n),read(m);
	for (int i=1;i<=m;i++)
	{
		int x,y,t;
		read(x),read(y),read(t);
		Addedge(x,y,t),Addedge(y,x,t);
		e1[i].x=x,e1[i].y=y,e1[i].t=t;
	}
	spfa();
	tot=0;
	for (int i=1;i<=m;i++)
	{
		int x=e1[i].x,y=e1[i].y,t=e1[i].t;
		if (fa[x]!=y&&fa[y]!=x)
		{
			E[++tot].x=x;
			E[tot].y=y;
			E[tot].v=d[x]+d[y]+t;
		}
	}
	sort(E+1,E+1+tot,cmp);
	for (int i=1;i<=n;i++)
		ans[i]=-1,f[i]=0;
	for (int i=1;i<=tot;i++)
	{
		Solve(E[i].x,E[i].y,E[i].v);
		if (now==n-1) break;
	}
	for (int i=2;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

感悟：

1.这道题的关键在于对非树边权值的转化，以及运用并查集快速往上爬

2.并查集复杂度应该是O(n)的吧？为什么会超时呢？？

【BZOJ 1576】 [Usaco2009 Jan]安全路经Travel