11078: 【原1078】Jerry的生日礼物

题目

题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1078

Description

幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y（因为小狗家Y离老鼠家X的距离

小于等于大狗家Z离老鼠家X的距离），再到大狗家Z，将两份礼物取回。

卡通城由N(\(3 \leq N \leq 200000\))个居住点和N-1条连接居住点的双向街道组成，经过第i条街道需花费Ti（1 ≤ Ti ≤ 1000000000）分钟的时间。

可以保证，任两个居住点间都存在通路。

不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？

定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。

给出卡通城的地图，找到一组X、Y、Z，使得：

|XY|≤|XZ|

|XY|+|YZ|最大。

并求出此时|XY|+|YZ|的值。

Input Format

第一行是两个整数N(\(3 \leq N \leq 200000\))和M（M=N-1），分别表示居住点总数和街道总数。

从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(\(1 \leq Ui, Vi \leq N\), \(1 \leq Ti \leq 1000000000\) )，表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。

Output Format

仅包含一个整数T，即|XY|+|YZ|的最大值

Hint

Source: NOI 2003

Sample Input

4 3
1 2 1
2 3 1
3 4 1

Sample Output

4

FineArtz's solution

/* Jerry的生日礼物 */
#include <iostream>
#include <cstring>
using namespace std;

class Edge{
public:
    Edge() = default;
    Edge(int uu, int vv, int ww, int nn) : u(uu), v(vv), w(ww), next(nn) {}

    int u = 0, v = 0, w = 0, next = 0;
};

Edge e[400005];
int head[200005], cnt = 0;
long long d1[200005] = {0}, d2[200005] = {0};
int n, m;

void addEdge(int u, int v, int w){
    e[++cnt] = Edge(u, v, w, head[u]);
    head[u] = cnt;
}

int distance(int x, long long *a){
    int ret = 0;
    bool v[200005] = {0};
    int q[200005], front = 0, rear = 0;
    a[x] = 0;
    v[x] = true;
    q[rear++] = x;
    while (front != rear){
        int now = q[front++];
        for (int i = head[now]; i != -1; i = e[i].next){
            int next = e[i].v;
            if (!v[next]){
                a[next] = a[now] + e[i].w;
                if (a[ret] < a[next])
                    ret = next;
                q[rear++] = next;
                v[next] = true;
            }
        }
    }
    return ret;
}

int main(){
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    int p1 = distance(1, d1);
    int p2 = distance(p1, d1);
    distance(p2, d2);
    long long ans = 0;
    for (int i = 1; i <= n; ++i){
        ans = max(ans, min(d1[i], d2[i]));
    }
    ans += d1[p2];
    cout << ans << endl;
    return 0;
}