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

### 题目描述

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

|XY|≤|XZ|

|XY|+|YZ|最大。

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

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(){
cin >> n >> m;
for (int i = 1; i <= m; ++i){
int u, v, w;
cin >> u >> v >> w;