題目大意: 給出一張無向連通圖，求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}
[cpp]
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 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次
[cpp]
while(k)
{
Martix(map,ant,ant);
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這條邊，實際上這條邊是不存在的
代碼:
[cpp]
//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;
}
