欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

和小哥哥一起刷洛谷(6) 图论之SPFA算法

程序员文章站 2022-03-02 18:08:55
...

关于\(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;
}

转载于:https://www.cnblogs.com/BlogE/p/luogu_day6.html