Skip to content

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;
}