题目描述：
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式：
第一行包含三个整数 n,m，s分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w表示一条 u →v 的，长度为 w 的边。
输出格式：
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31-1。
输入输出样例：
输入：
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
分析&说明：
学习了基础的松弛操作后，我们来学习最朴素的Floyd算法:
#include<iostream>
#include<cstdio>
using namespace std;
long long a[7005][7005],s,n,m,u,v,d;
const int inf=0x7fffffff;
int main()
{cin>>n>>m>>s;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=inf;//把邻接矩阵数组重置为inf}}for(int i=1;i<=m;i++){cin>>u>>v>>d;a[u][v]=min(a[u][v],d);//邻接矩阵存储}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){if(i==k||a[i][k]==inf){continue;}for(int j=1;j<=n;j++){a[i][j]=min(a[i][j],a[i][k]+a[k][j]);}//松弛操作}}a[s][s]=0; //起点标记为0for(int i=1;i<=n;i++){printf("%d ",a[s][i]);//输出}return 0;
}
然而我钟爱的Floyed在洛谷上只有40分。
所以只能用Spfa了！
Spfa代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,s;
struct node
{int to,next,w;
}a[510000];//邻接链表存图，来节省空间
int head[500100],vis[510000],dis[510000],st[510000];
int tot=0;
void init()
{memset(dis,0x3f,sizeof(dis));for(int i=1;i<=m;i++){head[i]=-1;}
}
void add(int u,int v,int w)
{a[++tot].to=v;a[tot].w=w;a[tot].next=head[u];head[u]=tot;
}
void spfa()
{int u,l=0;int r=1;st[1]=s;vis[s]=1;dis[s]=0;//上面几步为SPFA的初始化 while(l<r){u=st[++l];//队列的第一个元素出列，然后找该元素相连的其它点 vis[u]=0;//出列操作 for(int i=head[u];i!=-1;i=a[i].next){if(dis[a[i].to]>dis[u]+a[i].w)//如果新的边比原先的短，那就更新权值 {dis[a[i].to]=dis[u]+a[i].w;if(vis[a[i].to]==0)//如果被更新的点原先不在队列里，就把它加进来，这样做的好处是避免了每一个点的重复询问，降低了时间复杂度 {vis[a[i].to]=1;st[++r]=a[i].to;//被更新的点加入队列 }}}}
}
int main()
{int u,v,w;cin>>n>>m>>s;init();for(int i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);}spfa();//SPFA主体 for(int i=1;i<=n;i++){if(i==s) cout<<0<<" ";else{if(dis[i]==0x3f3f3f3f) cout<<2147483647<<" ";//如果没有被连，那就输出2147483647 else cout<<dis[i]<<" ";} }
return 0;
}
/* 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 */