高手去散步
高手 散步
2023-06-13 09:17:22 时间
思想:
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;
}
相关文章
- 硬核!GitHub置顶102W字Redis高手心法笔记,阿里竟第一时间收藏
- 【Redis高手修炼之路】数据类型——Redis的5种数据类型
- 【Redis高手修炼之路】案例——异步加载所有联系人
- PPT高手之路 笔记2
- 精通 MySQL 命令,成就 DBA 高手(mysql常用命令大全)
- 怎样学习Python,才能成为Python高手?
- Redis入门教程:从菜鸟到高手(redis菜鸟教程)
- 资本高手李东生
- 宁丽娟:改变行业格局的Oracle高手(宁丽娟oracle)
- 掌握即时Linux,步入技术高手行列(即时linux)
- 为什么高手离不了Linux系统?
- Linux LVM 教程:从初学者到高手的管理方法(linuxlvm教程)
- 掌握技巧,迈向专家之路——成为Linux高手必知的25个关键要点(如何成为linux高手)
- 让你成为Redis高手狂神的Redis笔记(狂神redis笔记pdf)