dfs+记忆化搜索,求任意两点之间的最长路径
搜索 路径 之间 最长 任意 DFS 记忆 两点
2023-09-14 08:56:54 时间
题意:n个点,m条边组成的有向图,求任意两点之间的最长路径
dfs记忆化搜索
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<vector>
#include<utility>
#include<map>
#include<queue>
#include<set>
#define mx 0x3f3f3f3f
#define ll long long
using namespace std;
int dis[1005],way[1005][1005],vis[1005],flag[1005];
int n,m;
int dfs(int x)
{
if(vis[x]==1)
return dis[x];
for(int i=1;i<=n;i++)
{
if(way[x][i]!=0)
dis[x]=max(dis[x],dfs(i)+way[x][i]);//dis[x]表示以x为起点能走的最长路径是dis[x]
}
vis[x]=1;
return dis[x];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
flag[y]=1;//标记终点
if(way[x][y]!=0)
way[x][y]=max(way[x][y],z);
else
way[x][y]=z;
}
int ans=0;
for(int i=1;i<=n;i++)//枚举搜索起点
{
if(flag[i]==0)//给的是有向图,只能从有向图的起点开始搜索
ans=max(ans,dfs(i));
}
cout<<ans<<endl;
return 0;
}
/*
5 5
1 2 15
2 3 12
1 4 17
4 2 11
5 4 9
6 6
1 2 2
4 5 2
2 3 3
1 3 2
5 6 2
1 2 4
*/
相关文章
- 04-树4 是否同一棵二叉搜索树 (25分)
- 移动端搜索的设计技巧!
- 理解Lucene索引与搜索过程中的核心类
- Java实现 LeetCode 212 单词搜索 II
- Linux动态库(.so)搜索路径
- LUA require 搜索路径指定方法
- 数据结构与算法-2 最短路径 Dijkstra A*搜索 [MD]
- Linux动态库(.so)搜索路径
- C/C++ 头文件以及库的搜索路径
- LeetCode-449. 序列化和反序列化二叉搜索树【前序遍历,二叉搜索树】
- ( “树” 之 BST) 669. 修剪二叉搜索树 ——【Leetcode每日一题】
- C#中实现对Excel特定文本的搜索
- SAP CRM的WITH_INDOBJECTS搜索参数问题
- SAP CRM Fiori 标准应用 My Account - search by ID 根据 ID 进行搜索的标准功能实现原理
- 基于GA算法的TSP最短路径搜索matlab仿真
- 【Struts2学习笔记(1)】Struts2中Action名称的搜索顺序和多个Action共享一个视图--全局result配置
- 改进基于优先队列的最短路径搜索『洪水流思想的体现』
- L34.linux命令每日一练 -- 第五章 Linux信息显示与搜索文件命令 -- echo和watch
- L31.linux命令每日一练 -- 第五章 Linux信息显示与搜索文件命令 -- uname和hostname
- C语言使用技巧(二十二):算法技巧:while(1)与if循环的循环扣圈搜索与路径节点搜索
- google搜索 site:pku.edu.cn inurl:aspx 即可查找所有动态网页 =====html(静态网页) asp(动态) jsp(动态) php(动态) cgi(网络程序) aspx(动态)
- 悟空分词的搜索和排序源码分析之——搜索
- 【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
- m分别使用Dijkstra算法和Astar算法进行刚体机器人最短路径搜索和避障算法的matlab仿真,带GUI界面
- C++算法之搜索算法一 深度优先搜索