题解 P1807 【最长路_NOI导刊2010提高（07）】

· · 题解

洛谷P1807题解

1、解题思路

鄙人不才，还没学过什么图论算法（SPFA什么的），只学过了DP。
DAG上的DP，总比那些算法简单。

那么具体思路到底是什么呢？

我们定义 dp(i) 为以 i 开头的最长路用 d[i] 来记录结果，然后用邻接表来储存数据，就可以了。

那么如何求dp(i)呢？遍历所有可以通向的边 （够通俗易懂），如果到不了终点，返回-1，否则返回长度。
详见代码。

还有最重要的一点，即我错3次的这一点，就是两个点之间可以有两条边，每次要取最大的。

2、解题代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1500+5;
long long G[N][N];//邻接表
long long d[N];
int n;

long long dp(int x){
    long long& ans=d[x];
    if(ans>=0)return ans;//记忆化，这个算过了
    if(n==x)return ans=0;//到达终点
    for(int i=1;i<=n;i++){
        if(G[x][i]&&dp(i)!=-1)ans=max(ans,d[i]+G[x][i]);
        //如果答案不是无解
    }
    return ans;
}

int main(){
    memset(d,-1,sizeof(d));//全部赋值成-1不会WA
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        long long v;
        scanf("%d%d%lld",&a,&b,&v);
        G[a][b]=max(G[a][b],v);//坑点
    }
    printf("%lld",dp(1));
    return 0;
}