competitive-programming/dmoj/013-noi-03-p4-data-generator.cpp at main · UnknownHacker1/competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
 * NOI '03 P4 - Data Generator  [noi03p4]
 * Problem:  https://dmoj.ca/problem/noi03p4
 * Verdict:  ACCEPTED (20.0 pts)   Solved: 2022-11-13
 * Language: C++20
 * Runtime:  0.363265619 s     Memory: 34792.0 KB
 * Source:   https://dmoj.ca/src/5029786
 */

/*
ID: BidoTeima
LANG: C++11
TASK:
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void moo(string filename);
void ACPLS(string str = "")
{
    if(str=="NOF")return;
    if(str.size())
        moo(str);
    else{
        #ifndef ONLINE_JUDGE
            freopen("output.txt", "w", stdout);
            freopen("input.txt", "r", stdin);
        #endif
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
void moo(string fileName){
    freopen((fileName+".in").c_str(),"r",stdin);
    freopen((fileName+".out").c_str(),"w",stdout);
}
#define tc         \
    int tttttt/*,subtask*/;    \
    cin >> tttttt/* >> subtask*/; \
    while (tttttt--)/*end
*/
bool vis[(int)2e5+3];
vector<pair<int,ll>>adj[(int)2e5+3];
ll dp[(int)2e5+3];
void dfs(int node, int prev, ll curdist){
    dp[node]=curdist;
    for(auto& child : adj[node]){
        if(child.first==prev)continue;
        dfs(child.first,node,curdist+child.second);
    }
}
bool vis2[(int)2e5+3];
int Y,Z;
ll curzdist;
void dfs2(int node, int prev, ll curdist){
    if(curdist>curzdist){
        curzdist=curdist;
        Z=node;
    }
    for(auto& child : adj[node]){
        if(child.first==prev)continue;
        dfs2(child.first,node,curdist+child.second);
    }
}
ll distFromY[(int)2e5+3],distFromZ[(int)2e5+3];
void dfs3(int node, int prev, ll curdist, bool YorZ){
    if(!YorZ)distFromY[node]=curdist;
    else distFromZ[node]=curdist;
    for(auto& child : adj[node]){
        if(child.first==prev)continue;
        dfs3(child.first,node,curdist+child.second,YorZ);
    }
}
int main()
{
    ACPLS("");
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int u,v,t;
        cin>>u>>v>>t;
        adj[u].push_back({v,t});
        adj[v].push_back({u,t});
    }
    dfs(1,-1,0);
    for(int i = 1; i <= n; i++){
        if(dp[i]>dp[Y]){
            Y=i;
        }
    }
    dfs2(Y,-1,0);
    dfs3(Y,-1,0,0);
    dfs3(Z,-1,0,1);
    ll ans=0;
    for(int X = 1; X <= n; X++){
        ll d1=distFromY[X];
        ll d2=distFromZ[X];
        ans=max(ans,min(d1,d2)+distFromZ[Y]);
    }
    cout<<ans;
}