Advertisement
Guest User

Untitled

a guest
Dec 28th, 2016
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. struct arco_t {
  8.     int u, v, w;
  9. };
  10. int N;
  11. vector<vector<arco_t>> G;
  12. int bfs(int start) {
  13.     vector<int> distances(N+1, -1);
  14.     vector<bool> visited(N+1, false);
  15.  
  16.     queue<int> coda;
  17.     coda.push(start);
  18.     distances[start] = 0;
  19.     int far = 0;
  20.     while (!coda.empty()) {
  21.         int nodo = coda.front();
  22.         coda.pop();
  23.         visited[nodo] = true;
  24.         for (auto x : G[nodo]) {
  25.             if (visited[x.v]) continue;
  26.             int cost = x.w + distances[nodo];
  27.             far = max(cost, far);
  28.             distances[x.v] = cost;
  29.             coda.push(x.v);
  30.         }
  31.     }
  32.     return far;
  33. }
  34.  
  35. int main() {
  36.     ifstream cin("input.txt");
  37.     ofstream out("output.txt");
  38.  
  39.     cin >> N;
  40.  
  41.     G.resize(N+1);
  42.  
  43.     for (int i = 1; i < N; i++) {
  44.         int a, b, l;
  45.         cin >> a >> b >> l;
  46.         G[a].push_back({a, b, l});
  47.         G[b].push_back({b, a, l});
  48.     }
  49.  
  50.     int longest = 0;
  51.     for (int i = 1; i <= N; i++) {
  52.         longest = max(bfs(i), longest);
  53.     }
  54.  
  55.     out << longest;
  56.     out.close();
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement