Как найти длину кратчайшего/длиннейшего пути в DAG через ДП по топологической сортировке?

В DAG нет циклов, поэтому вершины можно упорядочить топологически: каждое ребро ведёт «вперёд» по порядку. Тогда dp[v] (длиннейший путь, заканчивающийся в v) зависит только от уже обработанных предшественников — никакой циклической зависимости, ДП корректно.

int n;
vector<vector<pair<int,long long>>> g; // g[u] = {(v, weight), ...}
vector<int> order;          // топологическая сортировка (Kahn или DFS)
vector<long long> dp(n, 0); // dp[v] = длиннейший путь, кончающийся в v

for (int u : order)                 // в топологическом порядке
  for (auto [v, w] : g[u])
    dp[v] = max(dp[v], dp[u] + w);  // релаксация вперёд

long long ans = *max_element(dp.begin(), dp.end());

Для кратчайшего пути — то же самое, но dp инициализируем INF (источник = 0) и берём min. Это работает даже с отрицательными весами (в отличие от Дейкстры), потому что топопорядок гарантирует, что dp[u] финализирован до релаксации u → v.

Сложность $O(V + E)$ — линейно, и топосортировка, и проход по рёбрам. Для длиннейшего пути long long, чтобы не переполнить при больших весах.