今天主要把最短路径的spfa算法看完
首先要水的是盯了(N^N）天的黄油，，woc真的是。。。往后一翻书才知道这是用spfa。。。
顺便水一把spfa的膜版
bool f[N];
int d[N],q[N];
int head,tail;
void spfa(int s)
{
memset(d,10,sizeof(d));
<span style="white-space:pre"> </span>memset(f,0,sizeof(f));
<span style="white-space:pre"> </span>d[s]=0;<span style="white-space:pre"> </span>f[s]=true;
<span style="white-space:pre"> </span>head=0;tail=0;q[head]=s;
<span style="white-space:pre"> </span>for(;tail>=head;)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>int vv=q[head];
<span style="white-space:pre"> </span>for(int j=link[vv]; j; j=e[j].next)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if(d[vv]+e[j].v<d[e[j].y])<span style="white-space:pre"> </span>
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>d[e[j].y]=d[vv]+e[j].v;
<span style="white-space:pre"> </span>if(f[e[j].y]==false)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>tail++;
<span style="white-space:pre"> </span>f[e[j].y]=true;
<span style="white-space:pre"> </span>q[tail]=e[j].y;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>f[vv]=false;head++;
<span style="white-space:pre"> </span>}
}
其次呢就是也是历史遗留问题了，bfs
jzoj1193 很欢乐的一道图像题
找离0最近的1，预处理之后用bfs膜版？