題目大意: 給出一張無向連通圖,求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}
經過k條邊的最短路,那麼我們只需要把這個代碼重復運行k次。
如果只想到這樣,肯定是不行的,K太大了。那麼我們可以把圖看成一個矩陣,每次求兩點間的最小值,就相當於用矩陣進行
一次特殊的乘法更新。然後用矩陣的k次冪來快速算出結果。
注意,INF一定要開到0x3fffffff。即(1<<30)-1;
#include#include #include #include using namespace std; #define INF ((1<<30)-1) int n; struct matrix { int mat[201][201]; matrix(){ for(int i=0;i<201;i++) for(int j=0;j<201;j++)mat[i][j]=INF; } }; int f[2001]; matrix mul(matrix A,matrix B) { matrix C; int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { C.mat[i][j]=min(C.mat[i][j],A.mat[i][k]+B.mat[k][j]); } } } return C; } matrix powmul(matrix A,int k) { matrix B; for(int i=1;i<=n;i++)B.mat[i][i]=0; while(k) { if(k&1)B=mul(B,A); A=mul(A,A); k>>=1; } return B; } int main() { matrix A; int k,t,s,e,a,b,c; scanf("%d%d%d%d",&k,&t,&s,&e); int num=1; while(t--) { scanf("%d%d%d",&c,&a,&b); if(f[a]==0)f[a]=num++; if(f[b]==0)f[b]=num++; A.mat[f[a]][f[b]]=A.mat[f[b]][f[a]]=c; } n=num-1; A=powmul(A,k); cout<