洛谷 P1294 高手去散步-邻接矩阵+dfs-求无向图的一条最长路径

输入:

4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60

输出:

150

邻接矩阵：
代码如下:

#include <iostream> using namespace std;int ans = -1; const int N = 25; int mp[N][N]; bool vis[N]; int n, m; void dfs(int u, int sum) {ans = max(ans, sum);for (int i = 1; i <= n; i++) {if (mp[u][i] > 0 && !vis[i]) {vis[i] = true;dfs(i, sum + mp[u][i]);vis[i] = false;}} }int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;mp[a][b] = c;mp[b][a] = c;}for (int i = 1; i <= n; i++) {vis[i] = true;dfs(i, 0);vis[i] = false;}cout << ans << endl;return 0; }

邻接表:
代码如下:

#include <iostream> #include <vector> using namespace std; const int N = 25;struct node {int from;int to;int w; }; int ans; bool vis[N]; vector<node>v[N];void dfs(int u, int sum) {ans = max(ans, sum);for (int i = 0; i < v[u].size(); i++) {if (!vis[v[u][i].to] && v[u][i].w > 0) {vis[v[u][i].to] = true;dfs(v[u][i].to, sum + v[u][i].w);vis[v[u][i].to] = false;}} }int main() {int n, m;cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;v[a].push_back({a, b, c});v[b].push_back({b, a, c});}for (int i = 1; i <= n; i++) {vis[i] = true;dfs(i, 0);vis[i] = false;}cout << ans << endl;return 0; }

总结

以上是生活随笔为你收集整理的洛谷 P1294 高手去散步-邻接矩阵+dfs-求无向图的一条最长路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。