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

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

*/