dfs+记忆化搜索,求任意两点之间的最长路径

C、Coolest Ski Route

题意: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
*/
上一篇:Jfrog Maven jenkins pipeline 流水线 培训 简单实验


下一篇:8636 跳格子(dfs+记忆化搜索)