算法作用
用来解决带负权的有向图的最短路问题。
只要跑一次spfa，就可以随便跑Dij了。
算法思想
给每条边重新安排一个边权，使得不再存在负权边，并且可以由新图的最短路结果快速推出原图的最短路结果。
不连通的对每个连通块可以分别求。所以我们只要考虑联通的情况下怎么做。
那么，我们可以回想一下k短路，在哪个里面我们有最短路树。而且图中非树边我们给他们赋予了一个新的权值，意义是如果加上这条边，最短路会变大多少。我们发现，这个值一定是正的。
然后，就很好玩了。你会发现这个东西，很裂项。因为他的表达式是(w_e dis_{e_{from}}-dis_{e_{to}})。
于是，就发现，所有(i)到(j)的路径，都是原来的路径长度再加上(dis_i-dis_j)。
赢了。
代码
#include<bits/stdc .h>
#define LL long long
#define MAXN 3100
#define MAXM 6100
#define MAXNUM 10000000
#define INF 1000000000
using namespace std;
template<typename T>void Read(T &cn)
{
char c;int sig = 1;
while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
while(isdigit(c = getchar()))cn = cn*10 c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn; cn/=10;
while(cn)cm = cm*10 cn,cn/=10,wei ;
while(wei--)putchar(cm 48),cm/=10;
putchar(cx 48);
}
struct qwe{
int a,b,ne,w;
void mk(int cn, int cm, int cx, int cw) {a = cn; b = cm; ne = cx; w = cw; }
};
struct qwer{
int a,b;
void mk(int cn, int cm) {a = cn; b = cm; }
inline friend bool operator <(qwer a, qwer b) {return a.b > b.b; }
};
qwe a[MAXM MAXN 1];
int alen;
int head[MAXN 10];
int n,m,p;
int vis[MAXN 1], lu[MAXN 1], dui[MAXNUM 1], l, r;
int ci[MAXN 1];
int lu2[MAXN 1];
qwer dui2[MAXM MAXN 1];
void lian(int cn, int cm, int cx) {a[ alen].mk(cn,cm,head[cn],cx); head[cn] = alen; }
void spfa(int cn)
{
l = r = 0;
memset(vis,0,sizeof(vis)); memset(ci,0,sizeof(ci));
dui[ r] = cn;
vis[0] = 1;
while(l < r)
{
int dang = dui[ l]; vis[dang] = 0;
ci[dang] ; if(ci[dang] > n) {p = 1; return; }
for(int i = head[dang];i;i = a[i].ne)
{
int y = a[i].b;
if(lu[y] <= lu[dang] a[i].w) continue;
lu[y] = lu[dang] a[i].w;
if(!vis[y]) dui[ r] = y, vis[y] = 1;
}
}
}
void dij(int cn, qwer dui[], int lu[])
{
for(int i = 1;i<=n;i ) lu[i] = INF;
lu[cn] = 0; int dlen = 0; dui[ dlen].mk(cn,0);
while(dlen)
{
while(dlen && dui[1].b != lu[dui[1].a]) pop_heap(dui 1,dui (dlen--) 1);
if(!dlen) break;
int dang = dui[1].a; pop_heap(dui 1,dui (dlen--) 1);
for(int i = head[dang];i;i = a[i].ne)
{
int y = a[i].b;
if(lu[y] <= lu[dang] a[i].w || !y) continue;
lu[y] = lu[dang] a[i].w;
dui[ dlen].mk(y,lu[y]); push_heap(dui 1,dui dlen 1);
}
}
}
int main()
{
Read(n); Read(m);
alen = 0; memset(vis,0,sizeof(vis));
for(int i = 1;i<=m;i ) {int bx,by,bz; Read(bx); Read(by); Read(bz); lian(bx,by,bz); }
p = 0; for(int i = 1;i<=n;i ) lu[i] = INF;
for(int i = 1;i<=n;i ) {if(lu[i] == INF) lu[i] = 0, spfa(i); if(p) {puts("-1"); return 0; } }
for(int i = 1;i<=m;i ) a[i].w = lu[a[i].a] - lu[a[i].b];
for(int i = 1;i<=n;i )
{
dij(i,dui2,lu2);
LL ans = 0;
for(int j = 1;j<=n;j ) ans = ans 1ll*j*(lu2[j] == INF ? INF : (lu2[j] - lu[i] lu[j]));
Write(ans); puts("");
}
return 0;
}