题解 单源最短路径 （SPFA）

# **P3371** ---- [题目链接](https://www.luogu.org/problemnew/show/P3371) (因为我太弱了,所以大佬还是不要吐槽了 : ),谢谢)--大佬席------> ---- # 算法 ---- 我们用一种非常腻害的算法——$SPFA$ # 先来一组样例:  # （起点为1） 用一个队列维护搜索的依次顺序，再用一个数组维护**目前从1号点到i号点的最短长度(权值)**，然后命名为vis。当目前不可以到达时，先调整为INF。当输出时判断:当最短距离==INF，输出2147483647。 对了，要记得 ```cpp vis[1]=0; ``` 然后可以开始搜了! (目前在队列中的点: $1$) ---- ## 开始搜索点1: **因为从1号点可以到达点2，且从点1到达点2的距离 $1+0$ 小于原本的距离 $INF$。所以我们更新vis[2]，并把点2加入队列。** 同理，调整vis[5]，把点5加入队列。  (目前在队列中的点: $2$,$5$) ---- ## 开始搜索点2: **因为从2号点可以到达点3，且从点1到达点3的距离 $4+1$ 小于原本的距离 $INF$。所以我们更新vis[3]，并把点3加入队列。** 同理，调整vis[4]，把点4加入队列。  (目前在队列中的点: $5$,$3$,$4$) ---- ## 开始搜索点5: **因为从5号点可以到达点3，且从点1到达点3的距离 $1+2$ 小于原本的距离 $4$。所以我们更新vis[3]，又因为点3已经加入了队列，所以不用重复加入。**  (目前在队列中的点: $3$,$4$) ---- ## 开始搜索点3: **因为从3号点~~可以到达幻想乡~~什么也不能到达，所以什么也没有发生QWQ。**  (目前在队列中的点: $4$) ---- ## 开始搜索点4: **虽然从4号点可以到达点5，但从点4到达点3的距离 $1+4$ 大于原本的距离 $2$。所以我们不用更新vis[3]。**  (目前在队列中的点:无) ---- 于是输出: ``` 0 1 3 4 2 ``` ## 算法部分完毕！ ---- # 建图 ---- 观察数据规模: **对于100%的数据：N<=10000，M<=500000** QWQ...... 考虑使用邻接矩阵... ```cpp int a[10010][10010]; ``` ~~点一下有惊喜~~ [](https://www.luogu.org/recordnew/show/8094663) QWQ...... 好吧，不说了，加入正题： # 新的建图方法——链式前向星！！！ ~~已经会了的dalao们就跳过吧QWQ~~ ---- 窝不想讲吗~~~(捂脸)人家不想讲吗 [戳一下](http://baidu.apphb.com/?q=%E9%93%BE%E5%BC%8F%E5%89%8D%E5%90%91%E6%98%9F) (窝还是提供一份链式前向星的代码吧~~~) ```cpp int head[maxn];//从i点出发的第一条边 struct egde{ int to,next_,w;//分别代表每条线目的地,下一条线的下标和权值 }a[maxm] //这样就可以用下列代码来依次把从now点出发的边遍历 for(i=head[now];i;i=a[i].next_) //是不是很神奇啊! //后面的是加入一条边的 void add(int u,int y,int o){ //建图 len++; c[len].next_=head[u]; c[len].to=y; c[len].dis=o; head[u]=len; } ``` ---- ## 我再放上代码吧！ ```cpp #include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int i,j,k,n,m,s,len; int vis[10010]; int dis[10010];//判断是否进队 int head[500010]; int dl[500010],l,r; struct stu{ int next_,to,w; }c[500010]; void add(int u,int y,int o){ //建图 len++; c[len].next_=head[u]; c[len].to=y; c[len].w=o; head[u]=len; } void SPFA(){ //初始化 for(i=1;i<=n;i++){ vis[i]=INF; } vis[s]=0; l=0;r=1;dl[r]=s;dis[s]=1; //设置队列 while(l^r/*没用的位运算,也就是j!=r*/){ l++; int u=dl[l]; dis[u]=0; for(i=head[u];i;i=c[i].next_){//遍历每条从i点出发的边 int v=c[i].to; if(vis[v]>vis[u]+c[i].w){//如果路径长度小于原长度 vis[v]=vis[u]+c[i].w;//调整 if(!dis[v]){ //入队 dis[v]=1; r++; dl[r]=v; } } } } } int main(){ cin>>n>>m>>s; //输入 for(i=1;i<=m;i++){ int u,y,o; scanf("%d%d%d",&u,&y,&o); add(u,y,o); } SPFA(); //输出 for(i=1;i<=n;i++) if(vis[i]==INF)cout<<2147483647<<" "; else cout<<vis[i]<<" "; return 0; } ```