编程开发练习题_求最长路径

主题思想： 我用的是记忆化搜索，网上其他人用的是求最长路径。 记忆化搜索也不难，主要是，开数组，记录结果。
；另外，这题在输出路径上花了时间， 输出超时ＯＬＥ，最后解决办法是，把一些设置为最小值的数，设置的尽可能小。

要注意 dijkstra不能求最长路径， 单源最短路径ＳＰＦＡ算法，可以处理负权边。实现起来还算简单。

ＳＰＦＡ算法代码：

queue q;
int start;
q.push(start);

while(!q.empty()){
    int now=q.front();
    q.pop();
    // update all node  这里是重点，更新所有节点
    for(int i=0;i
记忆化搜索代码：
#include 
#include
#include
#include
#include
#include
using namespace std;

const int maxn=105;
vector g[maxn];  //the graph
int p[maxn];          // the points
int n;
int route[maxn];     //remember the route
int a[maxn];  // remember search


void showRoute(){

    int v=1;
    while(v!=route[v]){

        printf("%d->",v);
        v=route[v];
    }
}

int  dfs(int v){

    if(v==n+1){
        a[v]=0;
        route[v]=v;
        return 0;
    }

    if(a[v]>-1) return a[v];
    int mindex=-10000;
    int len=g[v].size();
    int next;
    int mx=-1000000;
    for(int i=0;i-1){
          if(p[v]+a[next]>mx){

            mx=p[v]+a[next];
            mindex=next;
          }
        }
        else{
            if(p[v]+dfs(next)>mx){

                mx=p[v]+a[next];
               mindex=next;
            }
        }
    }
    a[v]=mx;
    route[v]=mindex;
    return a[v];
}


int main()
{
    int T;
    scanf("%d",&T);
    int m;
    int from,to;
    int t=T;
    while(T--){

        scanf("%d",&n);

        for(int i=1;i<=n;i++){

            scanf("%d",&p[i]);

            g[i].clear();
        }
        g[n+1].clear();
        p[n+1]=0;

        scanf("%d",&m);
        for(int i=0;i0)printf("\n");
    }
    return 0;
}