โจทย์ข้อนี้เป็นแนว Graph ที่ตรงไปตรงมา เนื่องจากถนนเชื่อมเมืองมีเพียง $N - 1$ เส้น แปลว่า Simple Path (Path ที่ไม่มีจุดยอดซ้ำกัน) จากเมืองหมายเลข $1$ ไปยังเมืองหมายเลข $i$ ใดๆ $(1 \leq i \leq N)$ จะมีเพียงแบบเดียว

การหาระยะทางที่ไกลที่สุดที่สามารถเดินทางจากเมืองหมายเลข 1 ไปยังเมืองที่ไกลที่สุดนั้น สามารถทำได้ด้วยวิธี DFS หรือ BFS

Solution Code

#include <bits/stdc++.h>

using namespace std;
const int MXN = 1e5 + 5;

vector<pair<int, int>> edge[MXN];
bool pass[MXN];

int main() {
  int n, ans = -1;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    edge[u].emplace_back(v, w);
    edge[v].emplace_back(u, w);
  }
  queue<pair<int, int>> q;
  q.emplace(0, 1);
  pass[1] = true;
  while (q.size()) {
    int weightnow = q.front().first;
    int idxnow = q.front().second;
    ans = max(ans, weightnow);
    q.pop();
    for (auto i : edge[idxnow]) {
      if (!pass[i.first]) {
        q.emplace(weightnow + i.second, i.first);
        pass[i.first] = true;
      }
    }
  }
  printf("%d", ans);
}

Time Complexity: $\mathcal{O}(N)$