给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
1 2 -1
2 3 -1
3 1 2
-2
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
我在网上搜索了最短路算法，发现基本有4种。
1.floyd 算法 2.dijkstra算法 3.bellman算法 4.spfa算法
floyd算法时间复杂度高，dijkstra算法不能计算带负边权的图，故均不考虑。
spfa算法是bellman的一种优化，所以决定从简单的先开始。
bellman实现的代码如下：
#include <iostream>#include<string.h>
using namespace std;
int dis[20005],u[200005],v[200005],w[200005];//dis[i]代表第一点到第i点距离，u[i]，v[i],w[i]分别代表第i条边的起始点，终点和长度。
int main()
{
int m,n;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u[i]>>v[i]>>w[i];
}
memset(dis,10001,sizeof(dis));
dis[1]=0;
for(int k=1;k<n;k++)//最极端的情况下，一个点要松弛n-1次
{
for(int i=1;i<=m;i++)//枚举所有的条边
{
if(dis[v[i]]>dis[u[i]]+w[i])
//如果第一点到v[i]点的距离大于第一点到u[i]再加上u[i]到v[i]的距离
dis[v[i]]=dis[u[i]]+w[i];//说明dis[v[i]]的值可以更小，所以更新dis[v[i]]的值，专业的说法就是进行了一次松弛操作
}
}
for(int i=2;i<=n;i++)
cout<<dis[i]<<endl;
}
这段代码很简 单，最关键的地方在两层for循环的那部分。算法的时间复杂度显然是O(mn),最后提交超时。
SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。
SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的，k是一个常数，在稀疏图中小于2)。
但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。
实现方法：建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
此外，SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。
#include <iostream>#include<string.h>#include<queue> using namespace std;struct edge{ int to,val,next;}e[200100];//e[i].to,e[i].val,e[i].next分别表示第i条边的终点，权值，和另（上）一条于此边相同起点的边的编号int m,n,head[21000],dis[21000];//head[i]表示当前以i为起点的边的编号，dis[i]表示1号点到i号点的距离void add(int from,int to,int val,int len)//添加边，参数分别代表此边的起点，终点，权值，还有此边的编号{ e[len].to=to; e[len].val=val; e[len].next=head[from];//此边的起点是from，而head[from]保存上一条起点是from的边的编号 head[from]=len;//添加了这条边后，现在，最新的以from为起点的边编号就是len}void spfa(){ int s; queue <int> q; int visit[21000];//visit[i]==0代表第i点不在队列中，visit[i]==1代表已在队列中 for(int i=1;i<=n;i++) { dis[i]=99999999; }//将权值初始化为最大值 memset(visit,0,sizeof(visit));//初始没有点在队列中 dis[1]=0; q.push(1); visit[1]=1;//现在把第一个点扔进队列 while(!q.empty())//如果队列不空则重复执行以下操作 { int t=q.front();//取队列的第一个元素 q.pop(); visit[t]=0;//t现在不在队列里 for(int i=head[t];i!=-1;i=e[i].next)//枚举所有以t为起点的边 { s=e[i].to;//s为所枚举的边的终点 if(dis[s]>dis[t]+e[i].val)//尝试松弛s点 { dis[s]=dis[t]+e[i].val; if(visit[s]==0) { q.push(s); visit[s]=1; }//如果成功松弛了s点，把s点扔进队列 } } } }int main (){ cin>>n>>m; int from,val,to; int len=1; memset (head,-1,sizeof(head)); for(int i=0;i<m;i++) { cin>>from>>to>>val; add(from,to,val,len); len++; } spfa(); for(int i=2;i<=n;i++) { cout<<dis[i]<<endl; }}