ABC317 C - Remembering the Days

■考えたこと
制約的に全探索と思った。
再帰で実装した。

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;
}