https://ac.nowcoder.com/acm/contest/329/B

题解：

std

作者：儒生雄才1
链接：https://ac.nowcoder.com/discuss/152781
来源：牛客网
 

有向无环图（DAG）上的最短路。
注意：负权值边的存在使得 Dijkstra 算法不适用，特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案。 考虑到 DAG 的特殊性，按照原图节点的拓扑顺序依次递推距离即可求解。

令𝑑𝑖表示节点1到i的最短路，𝑝𝑟𝑒𝑣_𝑖表示节点的先驱集合。则有：

di=min(dj+cost(j,i))其中𝑗∈𝑝𝑟𝑒𝑣_𝑖，其中𝑐𝑜𝑠𝑡(𝑗,𝑖)表示从节点j到节点i的有向边的边权。

按照节点拓扑顺序计算d即可。

时间复杂度：𝑂(𝑁+𝑀)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
struct Topo
{
    int n;
    int deg[MAXN];
    LL dist[MAXN];
    struct Edge
    {
        int to, value;
        Edge(int to, int value) : to(to), value(value) {}
    };
    vector<Edge> edges[MAXN];
    void init(int n)
    {
        this->n = n;
        memset(deg, 0, sizeof deg);
        for (int i = 1; i <= n; i ++)
            edges[i].clear();
    }
    void add_edge(int from, int to, int value)
    {
        edges[from].emplace_back(to, value);
        deg[to]++;
    }
    LL solve(int s, int t)
    {
        memset(dist, 0x3f, sizeof dist);
        dist[s] = 0;
        queue<int> q;
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 0) q.push(i);
        while (!q.empty())
        {
            int x = q.front();
            for (auto& i : edges[x])
            {
                dist[i.to] = min(dist[i.to], dist[x] + i.value);
                if (--deg[i.to] == 0) q.push(i.to);
            }
            q.pop();
        }
        return max(0LL, dist[t]);
    }
} res, zys;
int n, m;
int main()
{
    // freopen("Reszys.in", "r", stdin);
    // freopen("Reszys.out", "w", stdout);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        res.init(n), zys.init(n);
        for (int i = 1; i <= m; i ++)
        {
            int u, v, c, r, z;
            scanf("%d%d%d%d%d", &u, &v, &c, &r, &z);
            res.add_edge(u, v, c - r);
            zys.add_edge(u, v, c - z);
        }
        long long ans1=res.solve(1, n),ans2=zys.solve(1, n);
        if (ans1>ans2)
            printf("rip!!!\n%lld\n",ans1-ans2);
        if (ans1==ans2) printf("oof!!!\n");
        if (ans1<ans2) printf("cnznb!!!\n%lld\n",ans2-ans1);
    }
    return 0;
}