有 n 个数，给定m个约束条件，类似 xi−xj<=k 。 使最大差值最大。
不难看出这是一道差分约束的问题。 因为要使最大差值最大，所以先给任意一个值0，其他数给 INF ，刷最短路。 但是 zzkdalao 告诉我 POJ 这题卡 Spfa 的，于是我写了 Dij+heap 。
#include<cstdio> #include<cstring> #include<queue> #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; const int maxn=30005,maxm=150005; struct jz{ int id,x; bool operator<(const jz &b)const{return x>b.x;} }; priority_queue<jz> heap; inline int _read(){ int num=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar(); return num*f; } int n,m,dis[maxn]; int tot,lnk[maxn],son[maxm],w[maxm],nxt[maxm]; bool vis[maxn]; void add(int x,int y,int z){ nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;w[tot]=z; } int DIJ(){ memset(dis,63,sizeof(dis)); while (!heap.empty()) heap.pop(); heap.push((jz){1,0});dis[1]=0; while(!heap.empty()){ int x=heap.top().id;heap.pop(); while(vis[x]&&!heap.empty()) x=heap.top().id,heap.pop(); if (vis[x]) break; vis[x]=1; for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]&&dis[x]+w[j]<dis[son[j]]) dis[son[j]]=dis[x]+w[j],heap.push((jz){son[j],dis[son[j]]}); } int ans=0;for (int i=1;i<=n;i++) ans=max(ans,dis[i]-dis[1]); return ans; } int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); n=_read(),m=_read(); for (int i=1;i<=m;i++){ int x=_read(),y=_read(),z=_read(); add(x,y,z); } return printf("%d\n",DIJ()),0; }