P1031 （C++代码）

解题思路:





注意事项:





参考代码:

刚学Ford

本来可以用队列优化的

于是为了对以后像我这样的蒟蒻有好一点

我打算发一个Ford的题解

关于Ford的思想我就略微讲下吧

首先 松弛是最重要的

那我们先考虑一条边

用dis[i]存到i的最短距离

初始化时将dis[i]全部存为INF

u[i],v[i],w[i]代表u[i]到v[i]的距离为w[i]

则会有下面这个式子

if(dis[v[i]]>dis[u[i]]+w[i])

    dis[v[i]]=dis[u[i]]+w[i];

而这是处理有向图的

所以对于这道无向图的题

我们还需要一次。

if(dis[u[i]]>dis[v[i]]+w[i])

    dis[u[i]]=dis[v[i]]+w[i];

那么一共有n条边的话

就要对n条边进行松弛

如果我们把上述记为一次松弛的话

那么我们一共就要进行总点数-1次松弛

因为两点之间的最短路径最多就包括总点数-1条边

恩 思路讲完了

那我就贴代码了

有一点点注释。

#include<iostream>
using namespace std;    
const int MAXN=6200+5;    
const int INF=2e9;    
int u[MAXN],w[MAXN],v[MAXN],dis[2501],s,e,m,n;    
bool check;//这个变量可以让我们进行略微的优化
int main()
{        
   cin>>m>>n>>s>>e;//m个点，n条边
   for(int i=1;i<=n;i++)            
   cin>>u[i]>>v[i]>>w[i];        
   for(int i=1;i<=m;i++)
   dis[i]=INF;
   dis[s]=0;//到起点的最短距离为0
   m--;//一共进行m-1次松弛，可以优化时间
   for(int j=1;j<=m;j++)
   {
       check=true;//每一次松弛将这个变量都给true
       for(int i=1;i<=n;i++)
            {             
        if(dis[v[i]]>dis[u[i]]+w[i])
            {
              dis[v[i]]=dis[u[i]]+w[i];
              check=false;
             }                
            if(dis[u[i]]>dis[v[i]]+w[i])
                {
                    dis[u[i]]=dis[v[i]]+w[i];
                    check=false;

}//如果dis在松弛中没有发生变化，直接结束（因为已经求出了最短路径啊）

}                
            if(check)    
              break;
        }    
        cout<<dis[e];//输出
}