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

· · 题解

【思路】

拓扑排序 + DP
不过这道题必须要求的1到n这两个点之间的最长路
所以不能吧入度为0的点都放进去
而是应该只放进去1
对其他的入度为0但是不是1的点怎么处理呢？
枚举完1能到达的点并且减去入度之后
这些点不一定会为0
所以需要将那些多余的点删掉
这里的删掉指的是入度--
也就是把除了1以外的入度为0的点
进行拓扑排序
拓扑排序到的点就入度--
入度为0还是想像正常的拓扑一样放入栈/队列中去
直到栈/队列为空

然后再来一遍拓扑排序
只将1放入栈/队列中，
因为起点只能是1
在排序的过程中
可以进行DP
dp[i]表示i这个点到1的最长的距离
dp[i] = max(dp[i],dp[u] + w);
表示i这个点到1的最长距离等于max(它本身的值，他前一个点到1的最长距离+他和她前一个点之间的距离)

最后如果dp[n] == 0
也就是没有到达这个点
那就输出-1
否则输出dp[n]

【完整代码】

#include<iostream>
#include<cstdio>
#include<stack>
#define int long long
using namespace std;
const int Max = 50005;
struct node
{
    int y,w,ne;
}a[Max];
int head[1505],sum = 0;
int into[1505];
void add(int u,int v,int w)
{
    a[++ sum].y = v;
    a[sum].ne = head[u];
    a[sum].w = w;
    head[u] = sum;
}
stack<int>s;
int dp[1505];
stack<int>q;
signed main()
{
    int n,m;
    cin >> n >> m;
    int u,v,w;
    for(register int i = 1;i <= m;++ i)
    {
        cin >> u >> v >> w;
        add(u,v,w);
        into[v] ++;
    }
    int jj = 0;
    for(register int i = 1;i <= n;++ i)
        if(into[i] == 0 && i != 1)
            q.push(i);
    while(!q.empty())
    {
        int u = q.top();
        q.pop();
        for(register int i = head[u];i != 0;i = a[i].ne)
        {
            into[a[i].y] --;
            if(into[a[i].y] == 0)q.push(a[i].y);
        }
    }
    s.push(1);
    while(!s.empty())
    {
        int u = s.top();
        s.pop();
        for(register int i = head[u];i != 0;i = a[i].ne)
        {
            dp[a[i].y] = max(dp[a[i].y],dp[u] + a[i].w);
            into[a[i].y] --;
            if(into[a[i].y] == 0)s.push(a[i].y);
        }
    }
    if(dp[n] == 0)cout << -1;
    else    cout << dp[n] << endl;
    return 0;
}