传送门：点击打开链接
题意：有n个未知数，然后m条信息，每条信息有a，b，c，表示xb-xa<=c，求xn-x1的最大值(n<=3e4)
思路：差分约束，稍微总结了下
B-A<=C 转换成A->B的边权值为C
求B-A最大值转换为求A->B最短路
求B-A最小值转换为求B->A最短路并取负号
如果存在负环，则无解
如果不存在最短路，则无数解
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;struct Edge {int v, nxt, cost;
} E[MX << 1];
int Head[MX], erear;
int d[MX];
void edge_init(int n) {erear = 0;for(int i = 1; i <= n; i++) {Head[i] = -1;}
}
void edge_add(int u, int v, int cost) {E[erear].v = v;E[erear].cost = cost;E[erear].nxt = Head[u];Head[u] = erear++;
}
void dijkstra(int u, int n) {priority_queue<PII, vector<PII>, greater<PII> >Q;for(int i = 1; i <= n; i++) d[i] = INF;Q.push(PII(0, u)); d[u] = 0;while(!Q.empty()) {PII tp = Q.top(); Q.pop();int td = tp.first, u = tp.second;if(td > d[u]) continue;for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v, cost = E[i].cost;if(d[u] + cost < d[v]) {d[v] = d[u] + cost;Q.push(PII(d[v], v));}}}
}int main() {int n, m; //FIN;while(~scanf("%d%d", &n, &m)) {edge_init(n);for(int i = 1; i <= m; i++) {int u, v, cost;scanf("%d%d%d", &u, &v, &cost);edge_add(u, v, cost);}dijkstra(1, n);printf("%d\n", d[n]);}return 0;
}