本文最后更新于 716 天前,其中的信息可能已经有所发展或是发生改变。
思想:
DFS
。- 题目所给出的路径可以连接为一个无向图。
- 则利用邻接矩阵来存图,从 1 号点开始,深度优先遍历所有的点。
- 走过的路径长度用
cnt
保存,最后维护最长的res
即可。
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e2 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); int mp[N][N]; bool vis[N]; int n, m, res; void dfs(int x, int cnt){ res = max(res, cnt); for(int i = 1; i <= n; i ++){ if(mp[x][i] != 0 && !vis[i]){ vis[i] = 1; dfs(i, cnt + mp[x][i]); vis[i] = 0; } } } void solve(){ cin >> n >> m; for(int i = 0; i < m; i ++){ int a, b, c; cin >> a >> b >> c; mp[a][b] = mp[b][a] = c; } for(int i = 1; i <= n; i ++){ memset(vis, 0, sizeof vis); vis[i] = 1; dfs(i, 0); } cout << res << endl; } int main(){ IOS; int _ = 1; // cin >> _; while(_ --){ solve(); } return 0; }