最短路问题之SPFA
Mudrobøt
2018-01-01 16:46:28
###P3371 【模板】单源最短路径 题解
**这是一道蛋蛋的题，我用SPFA干掉了他，可是又因为老毛病if没打两个等号，这道题又成功的耗费了我20分钟！**
####下面上源代码（内有注释）：
```cpp
//SPFA
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct sd{
int len,num;//len代表长度，num代表到达点的编号
}lin;
queue<int> q;//队列操作
vector<sd> edge[10005]; //存储每一个点到达另一个点的编号，和他们之间的长度
int n,m,s;
bool vis[10005];//数组变量vis判断元素是否在队列中false代表不再，true代表在。
int dis[10005];//存储当前从起点到达该点的最短距离。
void init();
void outit();
int main()
{
init();
vis[s]=true;
q.push(s);
dis[s]=0;
//--------------------我是华丽的分割线 --------------------\\
//SPFA主程序
while(!q.empty())//切记：SPFA是Bellman-Ford的队列优化，所以一定有队列操作
{//☣
int now;
now=q.front();
q.pop();//出队
for(int i=edge[now].size()-1;i>=0;--i)
{
if(dis[edge[now][i].num]>dis[now]+edge[now][i].len)//更新(详细变量说明见上)
{
dis[edge[now][i].num]=dis[now]+edge[now][i].len;
if(vis[edge[now][i].num]==false)//入队操作
{
vis[edge[now][i].num]=true;
q.push(edge[now][i].num);
}
}
}
vis[now]=false;//更改变量vis
}
//--------------------我是华丽的分割线 --------------------\\
outit();
return 0;
}
void init()//输入
{
//memset(dis,0x7f7f7f7f7f,sizeof(dis));
for(int i=1;i<=10000;++i)
{
dis[i]=2147483647;
}
scanf("%d%d%d",&n,&m,&s);
int a,b,c;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&lin.len);
lin.num=b;
edge[a].push_back(lin);//注意(caution):这里的图是有方向的，所以不能双向Push_down()
}
}
void outit()//输出
{
for(int i=1;i<=n;++i)
{
printf("%d ",dis[i]);
}
}
```