差分约束

以 $dist[i]$ 表示从源点到点 $i$ 的最短路，有一条边从 $v$ 到 $u$，边权 $e$，则 $dist[u]\le dist[v]+e$,即 $dist[u]-dist[v]\le e$。

包括 $a-b\le c,a-b\ge c,a=b$ 类不等式的不等式组，可转化为最短、长路问题（以最短路为例）：

设 $a,b$ 的值为 $dist[a],dist[b]$

$a-b\le c\to$ 有一条边从 $b$ 到 $a$，边权为 $c$ 。

$a-b\ge c\to$ 有一条边从 $a$ 到 $b$，边权为 $-c$。

$a=b\to a\le b,a \ge b\to $ $a,b$ 间互相各有一条边权为 $0$ 的边。

当图不连通，可通过隐含条件构造超级源点。

当图中存在负环时，不等式无解。（SPFA）

求出的一组解即为 $dist$。

Johnson 算法

用于求有负边稀疏图的全源最短路。

1. 任选一个节点，SPFA，求出每个点的 $dist$。
2. 将连接 $u\to v$ 的边边权更改为 $e+dist[u]-dist[v]$，$\because dist[u]+e\ge dist[v]$，$\therefore e+dist[u]-dist[v]\ge 0$
3. 选择每个节点为源点 dijkstra(队列优化)，将求出的源点 $i$ 点 $j$ 答案 $-dist[i]+dist[j]$
4. 时间复杂度：$O(mn+mn\lg m)$。

模板题，贴上代码一篇

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include <cstdlib>
using namespace std;
struct node
{
    int to,next,d;
}edge[10005];
struct NODE
{
    int p; long long di;
    friend bool operator < (NODE x,NODE y)
    {
        return x.di>y.di;
    }
};
int t[6005],n,m,dist[6005],cnt,cont[6005];
bool vis[3005],flag=0;
long long ans[3005][3005];
priority_queue <NODE> q;
queue<int>qq;
void create(int x,int y,int len)
{
    edge[++cnt].to=y;
    edge[cnt].next=t[x];
    edge[cnt].d=len;
    t[x]=cnt;
}
void spfa(int x)
{
    qq.push(x);
    vis[x]=1;
    dist[x]=0;
    cont[x]=1;
    while(!qq.empty())
    {
        int te=qq.front();
        qq.pop();
        vis[te]=0;
        for(int i=t[te];i;i=edge[i].next)
        {
            if(dist[edge[i].to]>dist[te]+edge[i].d)
            {
                if(!vis[edge[i].to])qq.push(edge[i].to),vis[edge[i].to]=1;
                dist[edge[i].to]=dist[te]+edge[i].d;
                cont[edge[i].to]=cont[te]+1;
                if(cont[edge[i].to]>n+1)
                {
                    flag=1;
                    return;
                }
            }
        }
    }
}

void dijkstra(int x)
{
    NODE aaa,aa;
    aaa.di=0;
    aaa.p=x;
    q.push(aaa);
    memset(vis,0,sizeof(vis));
    vis[x]=0;
    ans[x][x]=0;
    //printf(" q.size() = %d\n", q.size());
    while(!q.empty())
    {
        aaa=q.top();
        q.pop();
        //printf("aaa.p = %d\n", aaa.p);
        if(!vis[aaa.p])
        {
        vis[aaa.p]=1;
        //printf("aaa.p = %d\n", aaa.p);
        for(int i=t[aaa.p];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if(ans[x][y]>ans[x][aaa.p]+edge[i].d)
            {
                ans[x][y]=ans[x][aaa.p]+edge[i].d;
                aa.di=ans[x][y];
                aa.p=y;
                if(!vis[y])
                {
//                  printf("    aa.p = %d, aa.di = %d, aaa.p = %d, edge[i].d = %d\n", aa.p, aa.di, aaa.p, edge[i].d);
                    q.push(aa);
                    vis[y]=0;
                }
            }
        }
        }
    }
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=1000000000000000000LL;
    memset(dist,0x3f,sizeof(dist));//
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        create(a,b,c);
    }
    spfa(1);
    if(flag)
    {
        puts("-1");
        return 0;
    }
//  for(int i = 1; i <= n; i ++) {
//      printf("dist[%d] = %d\n", i, dist[i]);
//  }
    for(int i=1;i<=n;i++)
    {
        for(int j=t[i];j;j=edge[j].next)
        {
            edge[j].d=dist[i]-dist[edge[j].to]+edge[j].d;
//          printf("edge i = %d, to = %d, d = %d\n", i, edge[j].to, edge[j].d);
        }
    }
    for(int i=1;i<=n;i++)
    {
        dijkstra(i);
//      for(int j = 1; j <= n; j ++) {
//          printf("ans[%d][%d] = %d\n", i, j, ans[i][j]);
        //}
        //system("pause");
        long long anss=0;
        for(int j=1;j<=n;j++) {
            if(vis[j])
                anss+=1LL*j*(ans[i][j]-dist[i]+dist[j]);
            else
                anss+=j*1000000000LL;
        }
        cout<<anss<<endl;
    }
    return 0;
}