題目描述

給出一張無向連通圖，求S到E經(jīng)過k條邊的最短路。

輸入輸出樣例

輸入樣例#1：
2 6 6 4 11 4 6 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9 輸出樣例#1：
10
題解：
法1：dp+floyd+倍增
f[i][j][p]為從i到j(luò)經(jīng)過2^p條邊
顯然f[i][j][p]=min(f[i][k][p-1]+f[k][j][p-1])
如果n不是2的冪也沒事，將n進(jìn)行二進(jìn)制分解，再用dp轉(zhuǎn)移
ans[x][i]=min(ans[!x][j]+f[i][j][p]) n的二進(jìn)制第p位為1
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int n,t,s,e,f[201][201][25],ans[2][201],num[1005],pos,logn; 8 int main() 9 {int i,d,u,v,p,j,k; 10 cin>>n>>t>>s>>e; 11 memset(f,127/3,sizeof(f)); 12 memset(ans,127/2,sizeof(ans)); 13 for (i=1;i<=t;i++) 14 { 15 scanf("%d%d%d",&d,&u,&v); 16 if (!num[u]) num[u]=++pos; 17 if (!num[v]) num[v]=++pos; 18 f[num[u]][num[v]][0]=f[num[v]][num[u]][0]=d; 19 } 20 logn=log2(n); 21 for (p=1;p<=logn;p++) 22 { 23 for (k=1;k<=pos;k++) 24 { 25 for (i=1;i<=pos;i++) 26 { 27 for (j=1;j<=pos;j++) 28 { 29 f[i][j][p]=min(f[i][j][p],f[i][k][p-1]+f[k][j][p-1]); 30 } 31 } 32 } 33 } 34 t=0;p=0; 35 ans[0][num[s]]=0; 36 while (n) 37 { 38 if (n&1) 39 { 40 t=!t; 41 for (i=1;i<=pos;i++) 42 {ans[t][i]=2e9; 43 for (j=1;j<=pos;j++) 44 { 45 ans[t][i]=min(ans[t][i],ans[!t][j]+f[i][j][p]); 46 } 47 } 48 } 49 p++; 50 n/=2; 51 } 52 cout<<ans[t][num[e]]; 53 }

?

?

法二：矩陣乘法

可知用鄰接矩陣表示時(shí)，floyd的過程可以視為矩陣運(yùn)算，且滿足交換律

意思就是先求出走1條邊的矩陣，再求出找4條邊矩陣

等價(jià)于先求出走2條邊的矩陣，在求出找3條邊矩陣

重載矩陣乘法為floyd的過程，做快速冪就行

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int n,t,s,e,f[201][201],num[1005],pos; 8 struct mat 9 { 10 int s[101][101]; 11 mat() 12 {int i,j; 13 for (i=1;i<=pos;i++) 14 for (j=1;j<=pos;j++) 15 s[i][j]=1e9; 16 } 17 mat operator*(const mat &x) 18 {int i,j,k; 19 mat ans; 20 for (k=1;k<=pos;k++) 21 { 22 for (i=1;i<=pos;i++) 23 { 24 for (j=1;j<=pos;j++) 25 { 26 ans.s[i][j]=min(ans.s[i][j],s[i][k]+x.s[k][j]); 27 } 28 } 29 } 30 return ans; 31 } 32 }S,T; 33 int main() 34 {int i,j,d,u,v; 35 cin>>n>>t>>s>>e; 36 for (i=1;i<=t;i++) 37 { 38 scanf("%d%d%d",&d,&u,&v); 39 if (!num[u]) num[u]=++pos; 40 if (!num[v]) num[v]=++pos; 41 f[num[u]][num[v]]=f[num[v]][num[u]]=d; 42 } 43 mat S,T; 44 for (i=1;i<=pos;i++) 45 for (j=1;j<=pos;j++) 46 if (f[i][j]) 47 S.s[i][j]=T.s[i][j]=f[i][j]; 48 n--; 49 while (n) 50 { 51 if (n&1) 52 { 53 S=S*T; 54 } 55 T=T*T; 56 n>>=1; 57 } 58 cout<<S.s[num[s]][num[e]]; 59 }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Y-E-T-I/p/7366430.html

總結(jié)

以上是生活随笔為你收集整理的[USACO07NOV]牛继电器Cow Relays的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。