和小哥哥一起刷洛谷(6)

图论之SPFA算法

Posted by ethan-zhou on September 27, 2018

关于spfa

spfa伪代码:

void spfa(s){
    最短路数组全部设为无限大;
    队列 q;
    起点s入队;
    s离s的距离设为零;
    while(队列非空){
        取出队首;弹出队首;
        for(int i=0;i<u的出度;i++){
            v=第i个终点;
            w=到v的权值;
            if(到u点的最短路+w<目前到v点的最短路){//松弛
                更新目前到v点的最短路;
                v入队;
            }
        }
    } 
}

P3371 单源最短路径(弱化版)

题目描述:

如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入输出格式:

输入格式:

第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。

输出格式:

一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)

样例:

输入:

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出:

0 2 4 3

代码:

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
const int NR=100000;
int d[NR]/*最短路径存储列表*/,n,m,s;
vector< pair<int,int> > adj[NR];//一个结构体队列
void spfa(int s){//spfa函数
    memset(d,0x3f,sizeof(d));
    queue<int> q;
    q.push(s);d[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].first;
            int w=adj[u][i].second;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                q.push(v);
            }
        }
    } 
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;i++){
        int st,en,w;
        scanf("%d%d%d",&st,&en,&w);
        adj[st].push_back(make_pair(en,w));
    }
    spfa(s);
    for(int i=1;i<=n;i++){//输出
        if(d[i]>=1e9)printf("2147483647 ");
        else printf("%d ",d[i]);
    }
    return 0;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接