题目描述：
首先对于单点的情况可以用\(O(n\log n)\)，费用流算出来。
首先跑一边\(1\rightarrow i\)的最短路记作\(dis(i)\) 。
然后可能存在负环，不能直接跑dijkstra。但是可以把边权做一些修改\((u,v,w)\rightarrow (u,v,dis_u+w-dis_v)\) 。
然后再跑一边最短路，记作\(h(i)\).
\(h(i)\)的实际意义是当前最短路\(-\)上一次的最短路的差。
可以发现修改过的边权一定是正的。
然后跑出最短路树。
对于所有最短路树上的边无论有没有反转，最终都变成0 。
则可以每次删去\(h(i)\)最小的，然后更新每一个联通块内的信息。
每次舍去最大的，时间复杂度为\(O(m\log n)\) 。
code:
/*
{
######################
# Author #
# Gary #
# 2021 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<‘0‘||ch>‘9‘){
// ch=getchar();
// }
// while(ch>=‘0‘&&ch<=‘9‘){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=1e5+5;
vector<mp> g[MAXN];
vector<int> tree[MAXN];
vector<pair<int,LL > > g2[MAXN],rg[MAXN];
vector<int> tag[MAXN];
LL dist[MAXN];
LL dist2[MAXN];
bool era[MAXN];
int pre[MAXN];
int check(int now,int tot,int pre=0){
tot--;
if(tot==0) return 0;
for(auto it:tree[now]){
if(era[it]||it==pre) continue;
tot=check(it,tot,now);
if(tot==0) return 0;
}
return tot;
}
int cmp(int A,int B){
for(int x=1;x;x<<=1){
bool ok1,ok2;
ok1=check(A,x)!=0;
ok2=check(B,x)!=0;
if(ok1||ok2){
if(ok1) return B;
return A;
}
}
assert(0);
return 0;
}
int id[MAXN];
void lab(int now,int pre,int col){
id[now]=col;
for(auto it:tree[now]){
if(it!=pre&&!era[it]){
lab(it,now,col);
}
}
}
priority_queue<pair<LL,int> ,vector<pair<LL,int> > ,greater<pair<LL,int> > > heap;
LL S;
void upd(int now,int pre){
for(auto it:tree[now]){
if(it!=pre&&!era[it]){
upd(it,now);
}
}
for(auto it:g2[now]){
if(id[it.FIR]!=id[now]&&!era[it.FIR]){
if(dist2[it.FIR]>S+it.SEC){
dist2[it.FIR]=S+it.SEC;
heap.push(II(dist2[it.FIR],it.FIR));
}
}
}
for(auto it:rg[now]){
if(id[it.FIR]!=id[now]&&!era[it.FIR]){
if(dist2[now]>S+it.SEC){
dist2[now]=S+it.SEC;
heap.push(II(dist2[now],now));
}
}
}
}
void solve(){
int n,m;
scanf("%d%d",&n,&m);
fill(dist+1,dist+1+n,1e18);
fill(dist2+1,dist2+1+n,1e18);
fill(era+1,era+1+n,0);
fill(id+1,id+1+n,0);
rb(i,1,n) g2[i].clear(),g[i].clear(),rg[i].clear(),tree[i].clear(),tag[i].clear();
rb(i,1,m){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a].PB(II(b,c));
}
dist[1]=0;
heap.push(II(0,1));
while(!heap.empty()){
pair<LL,int> now=heap.top();
heap.pop();
if(dist[now.SEC]!=now.FIR) continue;
for(auto it:g[now.SEC]){
if(dist[it.FIR]>dist[now.SEC]+it.SEC){
dist[it.FIR]=dist[now.SEC]+it.SEC;
pre[it.FIR]=now.SEC;
heap.push(II(dist[it.FIR],it.FIR));
}
}
}
rb(i,1,n) if(pre[i]) tree[i].PB(pre[i]),tree[pre[i]].PB(i);
dist2[1]=0;
rb(i,1,n){
for(auto it:g[i]){
if(pre[it.FIR]==i){
assert(dist[i]-dist[it.FIR]+it.SEC==0);
g2[it.FIR].PB(II(i,0));
rg[i].PB(II(it.FIR,0));
tag[it.FIR].PB(1);
continue;
}
tag[i].PB(0);
g2[i].PB(II(it.FIR,dist[i]-dist[it.FIR]+it.SEC));
rg[it.FIR].PB(II(i,dist[i]-dist[it.FIR]+it.SEC));
}
}
heap.push(II(0,1));
while(!heap.empty()){
pair<LL,int> now=heap.top();
heap.pop();
if(dist2[now.SEC]!=now.FIR) continue;
era[now.SEC]=true;
S=now.FIR;
vector<int> Tmp;
rep(j,g2[now.SEC].size()){
auto it=g2[now.SEC][j];
if(!era[it.FIR]){
if(!tag[now.SEC][j]&&dist2[it.FIR]>dist2[now.SEC]+it.SEC){
dist2[it.FIR]=dist2[now.SEC]+it.SEC;
heap.push(II(dist2[it.FIR],it.FIR));
}
}
}
for(auto it:tree[now.SEC]){
if(!era[it]){
Tmp.PB(it);
}
}
if(!Tmp.empty()){
int biggest=Tmp[0];
rb(i,1,Tmp.size()-1){
biggest=cmp(biggest,Tmp[i]);
}
rep(i,Tmp.size()){
int id=Tmp[i];
if(id==biggest) continue;
lab(id,0,i+1);
}
for(auto it:Tmp){
if(it!=biggest){
upd(it,0);
}
}
rep(i,Tmp.size()){
if(Tmp[i]!=biggest)
lab(Tmp[i],0,0);
}
}
}
rb(i,2,n){
if(dist[i]>1e16||dist2[i]>1e16){
printf("-1");
}
else{
printf("%lld",dist[i]*2+dist2[i]);
}
if(i!=n) printf(" ");
}
puts("");
}
int main(){
int Z;
scanf("%d",&Z);
while(Z--) solve();
return 0;
}
XX Open Cup Grand Prix of Wroclaw I 题解
原文：https://www.cnblogs.com/gary-2005/p/14821561.html