首先我们要知道最短路问题的本质是：
1 11.从起点S出发到各个顶点v的最短距离是d [ v ] d[v]d[v]。
2. 对 于 每 条 权 值 为 w 的 边 e = ( v , u ) , 都 有 d [ v ] + w > = d [ u ] 成 立 2.对于每条权值为w的边e=(v,u),都有d[v]+w>=d[u]成立2.对于每条权值为w的边e=(v,u),都有d[v]+w>=d[u]成立。
3. 3.3.当所有满足以上的所有不等式的d中,d [ v ] − d [ s ] d[v]-d[s]d[v]−d[s]的最大值就是从S到V的最短距离(注意是最大值才是最短距离)
所有这些不等式两边都只出现一个变量，所以这种特殊不等式方程组叫做差分约束系统。
最短路就是一种差分约束系统
本题中:1.首先每个点已经按序号排成一排分配好了： d [ i + 1 ] + 0 > = d [ i ] d[i+1]+0>=d[i]d[i+1]+0>=d[i],可以连一条i + 1 i+1i+1指向i ii的权值为0的边，也可以不连，因为权值为0是不会进行松弛操作的
2. d [ A L ] + D L > = d [ B L ] 2.d[AL]+DL>=d[BL]2.d[AL]+DL>=d[BL],可以连一条由AL指向BL的权值为DL的边
3. d [ A D ] + D D < = d [ B D ] , 变 形 为 d [ B D ] − D D > = d [ A D ] 3.d[AD]+DD<=d[BD],变形为d[BD]-DD>=d[AD]3.d[AD]+DD<=d[BD],变形为d[BD]−DD>=d[AD],可以连一条由,BD指向AD的权值为-DD的边(负边)
此时处理出来的不等式约束条件完美符合差分约束系统，所以直接用spfa或者bellman_ford算法来求解
注意：判断无法满足约束条件,则从1到n的路上有负环（只要1到n没有负环就行了，其他地方有没有不重要
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N = 1e4 + 10, INF = 0x3f3f3f3f; struct edge { int to; int cost; }; int n, ml, md; vector<edge>g[N]; int d[N];//最小距离 bool st[N]; int cnt[N];//当1-v的路上边的个数cnt[v]>=n,则路上有大于等于n+1个点，但是一共只有n个点所以,此时必有负环 int spfa() { memset(d, 0x3f, sizeof(d)); st[1] = 1; queue<int>q; q.push(1); d[1] = 0; while (q.size()) { int t = q.front(); q.pop(); st[t] = 0; for (int i = 0; i < g[t].size(); i++) { edge x = g[t][i]; if (d[x.to] > d[t] + x.cost) { d[x.to] = d[t] + x.cost; cnt[x.to] = cnt[t] + 1;//更新边的个数 if (cnt[x.to] >= n) return -1; if (!st[x.to]) { st[x.to] = 1; q.push(x.to); } } } } return d[n]; } int main() { scanf("%d%d%d", &n, &ml, &md); for (int i = 1; i <= ml; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[x].push_back({y, z}); } for (int i = 1; i <= md; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); g[y].push_back({x, -z}); } int t = spfa(); if (t == -1) cout << -1 << "\n"; else if (t == INF) { cout << -2 << "\n"; } else { cout << t << "\n"; } return 0; }
求最小值，dv>=du+w,从u向v连w的边或者反方向连负边，求最长路。
求最大值，dv<=du+w,从v向u连w的边，求最短路。
注意从超级源点出发。
