■考えたこと
制約的に全探索と思った。
再帰で実装した。
ACしたコードは下記。
struct Edge { int to; ll cost; Edge(int to, ll cost) : to(to), cost(cost){} }; int main() { int n, m; cin >> n >> m; vector<vector<Edge>> g(n); for (int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; --a; --b; g[a].push_back(Edge(b, c)); g[b].push_back(Edge(a, c)); } vector<bool> visited(n); ll ans = 0; auto dfs = [&](auto dfs, int v, ll c) -> void { visited[v] = true; ans = max(ans, c); for (auto nv : g[v]) { if (visited[nv.to]) continue; dfs(dfs, nv.to, c + nv.cost); } visited[v] = false; }; for (int i = 0; i < n; i++) { dfs(dfs, i, 0); } cout << ans << endl; }