有一个时间复杂度O(n^2 log n)的做法，参见[桥](https://www.luogu.org/problemnew/show/P2685)，你把这题改一下就可以了
by wzporz @ 2018-07-06 15:21:34
```C++
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
#define gc getchar
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
inline ll read(){
register ll x=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
#define pc putchar
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 1005;
bool vis[maxn];
int d1[maxn],dn[maxn],pre[maxn];
int n,m;
int a[maxn][maxn];
void dijkstra(int S,int dist[]){
Rep(i,1,n) vis[i] = false;
Rep(i,1,n) dist[i] = inf;
dist[S] = 0;pre[S]=0;
Rep(i,1,n){
int k = -1;
Rep(j,1,n){
if(vis[j]) continue;
if(k == -1 || dist[k] > dist[j]) k = j;
}
vis[k] = true;
Rep(j,1,n){
if(vis[j]) continue;
if(dist[j] > dist[k] + a[k][j]){
dist[j] = dist[k] + a[k][j];
pre[j] = k;
}
}
}//进行n次迭代
}
vector<int> edge[maxn];
int fa[maxn];
int mx,pos[maxn];
inline int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
#define lson (o<<1)
#define rson ((o<<1|1))
int tag[maxn<<2];
void modify(int o,int l,int r,int x,int y,int v){
if(l==x&&r==y){tag[o] = min(tag[o],v);return ;}
int mid = (l + r) >> 1;
if(y<=mid) modify(lson,l,mid,x,y,v); else
if(mid+1<=x)modify(rson,mid+1,r,x,y,v); else{
modify(lson,l,mid,x,mid,v);
modify(rson,mid+1,r,mid+1,y,v);
}
}
void build(int o,int l,int r){
tag[o]=inf;
if(l==r)return;
int mid = (l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
}
int query(int o,int l,int r,int x){
if(l==r) return tag[o];
int mid = (l+r)>>1;
if(x<=mid) return min(query(lson,l,mid,x),tag[o]); else
return min(query(rson,mid+1,r,x),tag[o]);
}
int main(){
n = read(),m = read();
Rep(i,1,n)Rep(j,1,n) a[i][j] = inf;
Rep(i,1,m){
int x = read(),y = read(),v = read();
a[x][y] = a[y][x] = v;
}
dijkstra(n,dn);
dijkstra(1,d1);
Rep(i,1,n) fa[i] = pre[i];
mx = 0;
for(int i=n;i;i=pre[i]){
pos[i] = ++mx;
fa[i] = i;
if(pre[i])
a[i][pre[i]] = a[pre[i]][i] = inf;
}
build(1,1,n);
Rep(i,1,n){
Rep(j,1,n){
if(i==j) continue;
if(a[i][j] != inf){
int w = min(dn[i] + d1[j] + a[i][j],dn[j]+d1[i]+a[i][j]);
int x = pos[find(i)],y = pos[find(j)];
if(x>y)swap(x,y);
if(x==y) continue;
modify(1,1,mx,x+1,y,w);
}//有这样一个奇怪的东西
}
}
int ans = d1[n];
Rep(i,2,n) ans = max(ans,query(1,1,mx,i));
writeln(ans);
}
```
by wzporz @ 2018-07-06 15:22:57
另外，SPFA的复杂度是$O(nm)$，随便一张网格图就能卡。
by wzporz @ 2018-07-06 15:25:12
那是最坏情况吧
by Taduro @ 2018-07-06 19:36:25
不过我怎么记得堆优dijstra是n log n？
by Taduro @ 2018-07-06 19:37:20
看来我还是太菜了
by Taduro @ 2018-07-06 19:37:37
@[多弗桃](/space/show?uid=63661)
堆优化dijkstra正常写的化是$O(m log n)$
如果方便写每次判vis直接加的化是$O(m log m)$
如果用斐波那契堆可以优化到$O(m + nlogn)$
不要试图洗清$SPFA$
by wzporz @ 2018-07-06 22:44:17
@[东师附中旺仔](/space/show?uid=21182) 看来的确是我zz了，用邻接表的堆优dijkstra最坏确实是mlogn。
不过我这里还有一个小问题：要真有这么稠密的图为什么不用邻接矩阵写成nlogn？
by Taduro @ 2018-07-07 08:42:00
@[多弗桃](/space/show?uid=63661)
抱歉，这是$O(n^2)$的
by wzporz @ 2018-07-09 17:52:35