时间复杂度为O(MN)，适用于稀疏图，可以解决负权边，和边的关系密切
    #include
    using namespace std;
    const int N = 1e5+5;
    int u[N],v[N],w[N],dis[N];
    int main ()
    {
    int n,m,k;
    cin>>n>>m>>k;
    memset(dis,0x3f,sizeof dis);
    dis[k]=0;
    for (int i=1;i<=m;i++)
    cin>>u[i]>>v[i]>>w[i];
    for (int i=1;i for (int j=1;j<=m;j++)
    dis[v[j]]=min(dis[v[j]],dis[u[j]]+w[j]);
    for (int i=1;i<=n;i++)
    cout< return 0;
    }
    该算法还可以检测一个图是否有负权回路，如果在进行n-1轮松弛之后，仍然存在：
    dis[v[j]]>dis[u[j]]+w[j]，则表示该图存在负权回路。