点权（bfs，最短路，牛客练习赛93）

简化后的题意为：
给出节点数为 n n n 的一棵树，每条边有边权 c i c_i ci​。 ( n ≤ 1 0 5 , c i ≤ 1 0 3 ) (n le 10^5 ,c_i le 10^3) (n≤105,ci​≤103)
一个点必须由两个相邻的已更新的点更新，花费为两条边的边权之和。
初始入度小于2的节点（叶子节点）已更新。
对于每个点，求出能够将其更新的最小花费。如不可更新，输出-1。

从所有的叶子节点往中间更新，两个已更新的节点才能更新一个节点。求得到每个节点所需要的最小花费。
乍一看，是多源bfs，由所有的叶子节点往中间搜。
但是需要注意的是，两个节点才能更新一个节点。就是要选花费最少的两个相邻节点来更新当前节点。

• 于是就需要每个点都开一个小根堆，按照 点权+边权 将所有相邻已更新的点都存到小根堆中。
• 如果一个点的小根堆中至少有两个点了，说明这个点可以被更新了。于是就取花费最小的两个邻点（队首两元素）花费之和，放入最短路的优先队列中。
• 每次取优先队列队首元素，去更新与其相邻的点。

注意：如果优先队列的队首元素该出队了，那么能够更新这个点的所有相邻节点都一定在其小根堆中，并且队首元素这个的花费是最少的。
（这里参照dijkstra求最短路原理，只有一个点所有相邻已更新的节点都对其判断过之后，将其更新为最短距离，这个节点才会从优先队列中出队，去更新其他节点。也就是说，如果一个点出队了，那么这个点一定被更新为最短距离了。
而该点出队后，优先队列中可能还存有之前其他相邻点更新的非最短距离，如果这个非最短距离出队了，却发现这个点之前已经出队过了，已经更新过最短距离了，那么这个非最短距离就会跳过。这也就是为什么每个节点出队后，要将其 f 数组设为 true 的原因。）

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int e[N], ne[N], h[N], idx, w[N];
int ru[N], v[N], cost[N];
int f[N];

void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}

priority_queue, greater > q[N];

void bfs()
{
	priority_queue,greater > que;
	
	for(int i=1;i<=n;i++)  //所有叶子节点入队
		if(ru[i]<2) que.push({0,i});
	
	while(que.size())
	{
		int x=que.top().se, y=que.top().fi;
		que.pop();
		if(f[x]) continue;
		f[x]=1;
		
		cost[x] = y;
		
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int tx=e[i];
			
			q[tx].push(cost[x]+w[i]);
			
			if(q[tx].size()>1){		//取该点的小根堆的前两元素，放入优先队列
				int x=q[tx].top();
				q[tx].pop();
				que.push({x+q[tx].top(),tx});
				q[tx].push(x);
			}
		}
	}
}

signed main(){
	cin>>n;
	
	mem(h,-1);
	for(int i=1;i>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
		ru[x]++,ru[y]++;
	}
	
	bfs();
	
	for(int i=1;i<=n;i++)
		if(ru[i]<2) cout<<0<<" ";
		else if(q[i].size()>1) cout< 
 
用到了bfs的思想，dijkstra的实现，加上有点思维的每个点开一个小根堆。
 算是综合的一道图论题了。不错！