Bellman-Ford
此算法复杂度是O(NM)级别的所以在最短路里不是很受欢迎,如果不是这道题目的话应该不会用这个算法。
它的大概思想是把所有的边都遍历一遍不停去更新,直到更新不了为止。
(也正是因为这个性质才导致spfa效率更高。。。)
这种特殊的题目的话还是得回到此算法中,因为它可以控制踏板的个数。
也就是我们通过别的边来到达终点边的个数。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int sz=1e4+1;
struct nd{int x,y,z;}g[sz];
int n,m,k,d[sz],dd[sz];
void bl(int zx)
{
int i,j;nd a;
for(i=1;i<=n;++i)d[i]=1e9;d[zx]=0;
for(i=0;i<k;++i)
{
memcpy(dd,d,sizeof d);
for(j=0;j<m;++j)
{
a=g[j];
d[a.y]=min(d[a.y],dd[a.x]+a.z);
}
}
}
int main()
{
int i,x,y,z;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;++i)scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);
bl(1);
if(d[n]>=9e8+9e7+9e6+9e5+9e4+9e3+889)printf("impossible");//经过不懈努力刚好加这么多达到AC(再加就WA)
else printf("%d",d[n]);
return 0;
}
个人
这个算法我一直都没有在意过,因为有更简便且效率更高的SPFA。
直到了听了Y总的课才发现原来这个算法是有用的。。。
但是当我开始打模板我才发现一个问题我压根不是不屑去用这个算法而是我不会。。。
所以这算是第一次使用Bellman-Ford算法吧。