#include<iostream> using namespace std; const int V = 100; int n, m, ans, e[V][V]; bool visited[V]; void dfs(int x, int len) { int i; visited[x] = true; if (len > ans) ans = len; for (i = 1; i <= n; i++) if ((!visited[i]) && (e[x][i] != -1)) dfs(i, len + e[x][i]); visited[x] = false; } int main( ) { int i, j, a, b, c; cin >> n >> m; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) e[i][j] = -1; for (i = 1; i <= m; i++) { cin >> a >> b >> c; e[a][b] = c; e[b][a] = c; } for (i = 1; i <= n; i++) visited[i] = false; ans = 0; for (i = 1; i <= n; i++) dfs(i, 0); cout << ans << endl; return 0; }
输入:
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出:1