[백준 1167번] 트리의 지름

[백준 1167번] 트리의 지름

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

#include < iostream > #include < string > #include < algorithm > #include < queue > #include < vector > #include < stack > #include < utility > #include < climits > #include < deque > using namespace std ; vector < pair < int , int > > adj[ 100001 ]; bool visited[ 100001 ]; int n; int maxDist = 0 ; int start = 0 ; void dfs( int u, int dist) { visited[u] = true ; if (dist > maxDist) { start = u; maxDist = dist; } for ( auto v : adj[u]) { if (visited[v.first]) continue ; dfs(v.first, dist + v.second); } } void solve() { dfs( 1 , 0 ); maxDist = 0 ; fill(visited, visited + 100001 , 0 ); dfs(start, 0 ); cout < < maxDist; } int main( void ) { ios::sync_with_stdio( false ); cin .tie(nullptr); cin > > n; for ( int i = 1 ; i < = n; i + + ) { int u; cin > > u; while ( true ) { int v, c; cin > > v; if (v = = - 1 ) break ; cin > > c; adj[u]. push_back ({ v, c }); } } solve(); return 0 ; } Colored by Color Scripter

from http://seokjin2.tistory.com/84 by ccl(A) rewrite - 2021-12-16 01:01:05