Luogu 3371【模板】单源最短路径

第一次写博客用图论题来试一试

接下来是正文部分

题目描述

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

输入输出格式

输入格式：

第一行包含三个整数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

---

这道题目我是用spfa做的，所以我来说一下spfa的基本用法。

更稳定的算法详见

#include
    
     #define maxn 10000+5#define maxm 500000+5using namespace std;int la[maxm],ne[maxm],co[maxm],lnk[maxn],dis[maxn],tot=0,n,m,s,q[maxm*2];//la[],ne[],co[],lnk[]是邻接表用的数组,dis[]表示起始点到各点的距离,q[]是队列数组bool f[maxn];//f[i]表示i点是否在队中int read(){    char c=getchar();    while(c<'0'||c>'9')c=getchar();int x=0;    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();    return x;}void add(int x,int y,int z){    ne[++tot]=y;co[tot]=z;la[tot]=lnk[x];lnk[x]=tot;}//邻接表void spfa(int x){    for(int i=1;i<=n;i++)f[i]=true;//true表示该点没有在队中    for(int i=1;i<=n;i++)dis[i]=23333333;//初始化    int h=0,t=1;q[1]=x;f[x]=false;dis[x]=0;    while(h
     
      2333333)printf("2147483647 ");else printf("%d ",dis[i]);    return 0;}