本文最后更新于 548 天前,其中的信息可能已经有所发展或是发生改变。
思想:
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;
}