记忆化搜索

#include <bits/stdc++.h>
using namespace std;
const int INF = 1500 * 100000 + 1;
int n, m;
// <终点,权值>
vector<pair<int, int>> e[1505];
// vis 记录有没有算过，f 记录算出来的值
// 实际上这题用 -2 表示没算过也可以
bool vis[1505];
int f[1505];
// 返回 u 到 n 的最长路
int dfs(int u)
{
    if (vis[u] == true)
        return f[u];
    if (u == n)
    {
        vis[u] = true;
        return f[u] = 0;
    }
    int res = -INF; //-INF 表示走不到 n
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        int temp = dfs(v);
        if (temp == -INF)
            continue;
        // u->v->n：w+temp
        if (res == -INF || w + temp > res)
            res = w + temp;
    }
    vis[u] = true;
    return f[u] = res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    int ans = dfs(1);
    if (ans == -INF)
        cout << -1;
    else
        cout << dfs(1);
    return 0;
}

拓扑排序

#include <bits/stdc++.h>
using namespace std;
const int INF = 1500 * 100000 + 1;
int n, m;
// <终点,权值>
vector<pair<int, int>> e[1505];
vector<pair<int, int>> ee[1505]; // 反向边
int d[1505];                     // 入度
queue<int> q;                    // 存还没有处理的入读为 0 的点
vector<int> a;                   // 拓扑排序出来的序列
// f[i] 存从 i 到 n 的最长路
int f[1505];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        ee[v].push_back({u, w});
        d[u]++;
    }
    // 先反图中拓扑排序
    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        // 此时可以计算 u 的 f 值了
        // 但是这里为了看清楚，我把排好序的东西存下来
        a.push_back(u);
        // 把 u 连到的点的入度减少
        for (int i = 0; i < ee[u].size(); i++)
        {
            int v = ee[u][i].first;
            int w = ee[u][i].second;
            d[v]--;
            if (d[v] == 0)
                q.push(v);
        }
    }
    // 按照拓扑排序的结果求
    for (int i = 0; i < a.size(); i++)
    {
        int u = a[i];
        if (u == n)
            f[u] = 0;
        else
            f[u] = -INF;
        for (int j = 0; j < e[u].size(); j++)
        {
            int v = e[u][j].first;
            int w = e[u][j].second;
            // 此时我们知道 f[v] 已经算好了
            if (f[v] == -INF)
                continue;
            f[u] = max(f[u], f[v] + w);
        }
    }
    if (f[1] == -INF)
        cout << -1;
    else
        cout << f[1];
    return 0;
}