Codefores 374div2C Journey

Problem - C - Codeforces
まずはメモ化再帰解

#include <bits/stdc++.h>
using namespace std;

using edge = pair<int, int>;
const int INF = 1e9 + 10;
vector<edge> adj[5001];
int memo[5001][5001];
// memo[i][j] := dist to node[0][0]
short mae[5001][5001];
int dfs(short cur_v, int used) {
    int& res = memo[cur_v][used];
    if(res != -1) return res;
    res = INF;
    if(used <= 0) return res;
    for(auto e : adj[cur_v]) {
        int pre_v, cost;
        tie(pre_v, cost) = e;
        int tmp = dfs(pre_v, used - 1);
        tmp += cost;
        if(res > tmp) {
            res = tmp;
            mae[cur_v][used] = pre_v;
        }
    }
    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M, T;
    cin >> N >> M >> T;
    for(int _ : _in(M)) {
        int u, v, c;
        cin >> u >> v >> c;
        --u; --v;
        adj[v].emplace_back(u, c);
    }

    memset(memo, -1, sizeof(memo));
    memset(mae, -1, sizeof(mae));
    memo[0][0] = 0;
    int ans = 0;
    for(int i : _in(N, 0)) {
        int res = dfs(N - 1, i);
        if(res != -1 && res <= T) {
            ans = i; break;
        }
    }
    short cur = N - 1, tmp = ans;
    vector<short> vec;
    while(cur != -1) {
        vec.emplace_back(cur);
        cur = mae[cur][tmp];
        --tmp;
    }
    reverse(vec.begin(), vec.end());
    int S = vec.size();
    cout << S << '\n';
    for(auto x : vec) cout << x + 1 << ' ';
    cout << '\n';
    return 0;
}

次はトポロジカルソートしてDP

#include <bits/stdc++.h>
using namespace std;

struct Edge{ int to, cost;};
bool topologicalSort(vector<vector<Edge>>& adj, vector<int>& ord) {
    int N = adj.size();
    vector<int> deg(N);//入次数
    for(int i = 0; i < N; ++i)
      for(auto e : adj[i])
        ++deg[e.to];
    ord.assign(N, -1);
    int t = 0;
    for(int v = 0; v < N; ++v) 
      if(deg[v] == 0)
        ord[t++] = v;

    for(int h = 0; h < t; ++h) {
        int v = ord[h];
        for(auto e : adj[v]) {
            --deg[e.to];
            if(deg[e.to] == 0)
              ord[t++] = e.to;
        }
    }
    return t == N;
}


const int INF = 1e9 + 10;;
int main() {
    int V, E, T;
    scanf("%d%d%d", &V, &E, &T);
    vector<vector<Edge>> adj(V);
    for(int i = 0; i < E; ++i) {
        int u, v, t;
        scanf("%d%d%d", &u, &v, &t);
        --u; --v;
        adj[u].push_back({v, t});
    }
    vector<int> ord;
    topologicalSort(adj, ord);
    vector<vector<int>> dp(V, vector<int>(V + 1, INF));
    vector<vector<short>> preV(V, vector<short>(V + 1, -1));
    dp[0][1] = 0;
    for(int i : ord) {
        for(int j = 0; j < V; ++j) {
            if(dp[i][j] == INF) continue;
            for(auto e : adj[i])
              if(dp[i][j] + e.cost <= T)
                if(dp[e.to][j + 1] > dp[i][j] + e.cost)
                  dp[e.to][j + 1] = dp[i][j] + e.cost, preV[e.to][j + 1] = i;
        }
    }

    int num = 0;
    for(int i = V; i >= 0; --i) {
        if(dp[V - 1][i] < INF) {
            num = i;
            break;
        }
    }
    vector<int> ans;
    int cur = V - 1;
    while(cur != -1) {
        ans.emplace_back(cur);
        cur = preV[cur][num--];
    }
    reverse(ans.begin(), ans.end());
    int S = ans.size();
    printf("%d\n", S);
    for(int x : ans)
      printf("%d ", x + 1);
    puts("");
    return 0;
}

　トポロジカルソートは入次数が少ない順に番号づけする実装が効率よさそう（もちろんオーダーはDFSやBFSでも同じだが）だったのでこれにした。ただ入次数0の辺がスタート以外にもあって、スタートの番号が0じゃないとちゃんと動かないかもしれない。ゴールについても同様。
　トポロジカルソートがなんなのかよくわかっていなかったのだけど、結局すべての辺（有向辺）が→向きになるように頂点を並べ替えているらしい。
　こうするとなぜDPできるのかというと。頂点番号をループでまわすと、頂点iにいるとき、iを通る全ての経路について、iより前に通過する頂点番号はiより小さい。なので配るDPがキッチリ動作してくれる、ということだと思う。あまり自身はないけど。
　わかってしまえばDFS解はかなりかったるいようにも思える。実際（半分くらいはオーバーフローだけど）かなりWA出たし……。
［追記]
この時は半順序関係など、集合論の知識がなかった。悲しいなあ。