由于我刚刚了解邻接链表（不信自己看学术版），所以这里发一发题解，顺便重新理一遍
SPFA都应该了解，下面挂出框架
```
while 队列不为空
{
取队首，队首出队
枚举每一条边，如果起点为队首
对这条边进行一次松弛
（也就是三角形不等式dist[s]=min(dist[t]+map[s][t],dist[s])）
如果成功，入队
}
```
上面的是没有任何优化的朴素SPFA，显然，这种算法将有可能退化为BellmanFord
这时，我们使用一个全新的图存储方式~~，其实也不新~~
可以发现，这个算法最危险的地方就是枚举每一条边，如果能够直接知道要松弛哪些边，该多好啊！
这时就轮到邻接链表出场了。接下来介绍几个重要数组。
head[i]：起点是i的第一条边（其实大部分时候是最后一条，但是一般从这个head[i]开始搜索）
next[i]：表示第i条边同一起点的下一条边
to[i]：表示第i条边的终点
w[i]：表示第i条边的边权
研究完这些，离成功就不远了。首先看最重要的addedge函数
（注意是P，看得懂吧？）
```pascal
procedure addedge(u,v,w:longint);
begin
inc(tot); //边数增加
e[tot].too:=v; //设置终点为v
e[tot].l:=w; //边权
e[tot].nxt:=first[u]; //注意！将老的第一条边设置为新的的后继
first[u]:=tot; //新的第一条边
end;
```
以上就是这个算法的精华，设队首为u，接下来——
我们将SPFA中的枚举每一条边改为从head[u]开始，每次松弛，然后将u替换为next[u]，就可以啦！具体看代码吧
```pascal
var
e:array[0..500050] of record //结构体e，存to，w和next
too,l,nxt:longint;
end;
first,dist,q:array[0..500050] of longint; //head、dist、队列
flag:array[0..500050] of boolean; //队列标记
n,m,i,j,head,tail,s,t,f,g,w,p,tot:longint; //各种变量
function max(x,y:longint):longint; //max，用完cpp偶尔一次P觉得好麻烦
begin
if (x>y) then exit(x); exit(y);
end;
procedure addedge(u,v,w:longint); //边的构造
begin
inc(tot);
e[tot].too:=v;
e[tot].l:=w;
e[tot].nxt:=first[u];
first[u]:=tot;
end;
begin
readln(n,m,s,t);
for i:=1 to m do first[i]:=-1; //没有下一条边
tot:=0;
for i:=1 to m do
begin
readln(f,g,w);
addedge(f,g,w);
addedge(g,f,w); //双向！
end;
for i:=1 to n do dist[i]:=maxlongint; //将dist设置为极大值
dist[s]:=0; flag[s]:=true; q[1]:=s; //s入队列
head:=1; tail:=1;
while head<=tail do //while队列不为空
begin
p:=q[head]; inc(head); //出队
flag[p]:=false;
i:=first[p]; //找队首连出的边，首先是head[p]
while i>-1 do //找所有的边直到没有下一条边
begin
if dist[e[i].too]>max(dist[p],e[i].l) then //如果可以松弛
begin
dist[e[i].too]:=max(dist[p],e[i].l); //松弛
if not flag[e[i].too] then //入队列
begin
inc(tail);
q[tail]:=e[i].too;
flag[e[i].too]:=true;
end;
end;
i:=e[i].nxt; //下一条
end;
end;
writeln(dist[t]);
end.
```
有什么不足，欢迎拍砖