（模拟）吉林大学ACM集训队选拔赛（重现赛） I题 Firework

https://blog.csdn.net/qq_43497140/article/details/106820608 (csdn博客链接）

   这题直接多源bfs模拟下就好了，想清楚了就挺好写的，可惜比赛的时候没时间做这题了

    1.一个点u扩展到另一个点v，如果点v之前没扩展到，那t[v](第v个点最早点燃的时刻)=t[u]+2*w

    2.如果之前v已经被扩展到了，那如果t[v]>=t[u]+2*w,显而易见，t[v]可以更新成t[u]+2*w

    3.如果t[v]<t[u]+2*w,那说明uv在中间某个点相遇了，那相遇的时刻ans=max(t[u],t[v])+(2*w-abs((t[v]-t[u])))/2;

    然后所有ans（中间相遇时刻）和t[i]的最小值就是答案了

 
题目描述

Alice and Bob get a strange firework accidentally, and they never know how to play it, so they come to you for help.

The firework consists of n nodes and n-1 fuses connecting pairs of nodes. The whole firework forms an undirected tree. At the time 0, several nodes are ignited simultaneously. After that, the fire begins to spread through the fuses to all directions from those nodes which has been ignited. When the fire reaches another node that haven't been ignited before, it will ignite the node and keep spreading.

Fire has a specific speed. If the fuse has the length L, it needs 2L seconds to conduct the fire. Then the question comes: how long it will take to burn up the firework? We consider that the firework is burned up if and only if all the fuses are burned up.
输入描述:

The first line contains two integers n, m (1≤n,m≤105)(1\leq n,m\leq10^5)(1≤n,m≤105) -- the number of nodes of the firework and the number of nodes which are ignited initially.

This is followed by n-1 lines with fuse descriptions. Each fuse is given by three integers u, v and w (1≤u,v≤n,1≤w≤109)(1\leq u, v\leq n, 1\leq w \leq 10^9)(1≤u,v≤n,1≤w≤109), meaning that there is a fuse between node u and v with the length w.

The next line contains m distinct integers describing the ignited nodes' numbers.

输出描述:

Only one line with a single number T --  the time it takes to burn up the firework.

示例1
输入

复制3 2 1 2 1 2 3 2 1 3

3 2
1 2 1
2 3 2
1 3

输出

复制3

3

说明

For the first example, the fire reaches node 2 from the fuse (1,2) in 2 seconds. But the fuse (2,3) is still burning, the final answer is 3 seconds.

示例2
输入

复制5 2 1 2 5 2 3 1 2 4 2 4 5 1 1 4

5 2
1 2 5
2 3 1
2 4 2
4 5 1
1 4

输出

复制7

7

#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<set>
using namespace std;
#define ll long long
#define inf 1e9
#define maxn 301005
struct E
{
    ll to,w,next;
}e[maxn];
ll head[maxn],cnt,ans=0;
void add(ll u,ll v,ll w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
ll t[maxn];
struct node
{
    ll id;
    friend bool operator < (node n1, node n2)
    {
        return t[n1.id]>t[n2.id];//自定义优先级从大到小
    }
};
priority_queue<node>q;
ll n,m,vis[maxn];
void slove()
{
    for(ll i=1;i<=m;i++)
    {
        ll x;
        scanf("%lld",&x);
        q.push({x});
        t[x]=0;
    }
    while(!q.empty())
    {
        ll u=q.top().id;
        q.pop();
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            ll v=e[i].to,w=e[i].w;
            if(t[v]==-1)
            {
                t[v]=t[u]+2ll*w;
                q.push({v});
            }
            else if(t[u]+2ll*w<=t[v])
            {
                t[v]=t[u]+2ll*w;
            }
            else
            {
                ll h=max(t[u],t[v])+(2*w-abs((t[v]-t[u])))/2;
                ans=max(ans,h);
            }
        }
    }
    for(ll i=1;i<=n;i++) ans=max(ans,t[i]);
    printf("%lld\n",ans);
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(t,-1,sizeof(t));
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=n-1;i++)
    {
        ll u,v,w;
        scanf("%lld %lld %lld",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    slove();
}