题目链接: http://poj.org/problem?id=3613
题目大意: 给出一张无向连通图，求S到E经过k条边的最短路。
解题思路: 利用递推的思路，先算出经过一条边的最短路，再算两条边......k-1条边，k条边的最短路
先看一下Floyd的核心思想: edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
i到j的最短路是i到j的直接路径或者经过k点的间接路径，但是矩阵的更新总是受到上一次更新的影响
如果每次的更新都存进新矩阵，那么edge[i][k]+edge[k][j]是不是表示只经过三个点两条边的路径呢？
min(edge[i][j],edge[i][k]+edge[k][j])就表示只经过三个点两条边的最短路
方程：
F[i][j]m=min(F[i][k]m-1+G[k][j])
{1<=k<=n,m>1}
void Martix(martix &a,martix &b,martix &c) //传递指针
{
int i,j,j1;
memset(temp.edge,INF,sizeof(temp.edge)); //初始化为无穷大
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(j1=1;j1<=n;j1++)
if(temp.edge[i][j]>a.edge[i][j1]+b.edge[j1][j])
temp.edge[i][j]=a.edge[i][j1]+b.edge[j1][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c.edge[i][j]=temp.edge[i][j];
}
经过k条边的最短路，那么我们只需要把这个代码重复运行k次
while(k)
{
Martix(map,ant,ant);
k--;
}
这样显然答案是正确的，但是时间复杂度太高O(k*n^3)，利用二进制的思想可以把时间复杂度降到O(logK*n^3)
另外，存储边的邻接矩阵map.edge[i][i]不能初始化为0，为0时每次Floyd都会考虑走i--->i这条边，实际上这条边是不存在的
代码:
//k步最短路
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 202
#define INF 0x3f3f3f3f
typedef struct node{
int edge[MAX][MAX];
}martix;
martix ant,map,temp;
int n,num,f[MAX*100];
void Martix(martix &a,martix &b,martix &c) //传递指针
{
int i,j,j1;
memset(temp.edge,INF,sizeof(temp.edge)); //初始化为无穷大
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(j1=1;j1<=n;j1++)
if(temp.edge[i][j]>a.edge[i][j1]+b.edge[j1][j])
temp.edge[i][j]=a.edge[i][j1]+b.edge[j1][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c.edge[i][j]=temp.edge[i][j];
}
void Find(int k)
{
int i;
memset(ant.edge,INF,sizeof(ant.edge)); //***初始化矩阵,ant.edge[i][i]必需初始化为0***
for(i=1;i<=n;i++) //初始化后第一次与map“相加”,就等于map本身
ant.edge[i][i]=0;
while(k)
{
if(k&1)
Martix(map,ant,ant);
Martix(map,map,map);
k>>=1;
}
}
int main()
{
int i,k,s,e,m,a1,a2,a3;
scanf("%d%d%d%d",&k,&m,&s,&e);
memset(map.edge,INF,sizeof(map.edge)); //***初始化邻接矩阵,map.edge[i][i]不需要初始化为0***
memset(f,-1,sizeof(f));
for(i=0,num=0;i<m;i++)
{
scanf("%d%d%d",&a1,&a2,&a3);
if(f[a2]==-1) //离散化
f[a2]=++num;
if(f[a3]==-1) //离散化
f[a3]=++num;
map.edge[f[a2]][f[a3]]=map.edge[f[a3]][f[a2]]=a1;
}
n=num;
// for(i=1;i<=n;i++) //*****WA*****
// map.edge[i][i]=0;
Find(k);
printf("%d\n\n",ant.edge[f[s]][f[e]]);
return 0;
}
注:原创文章，转载请注明出处