图论专题训练1-D(K步最短路,矩阵连乘)
题目链接
/* *题目大意： *求出从i到j,刚好经过k条边的最短路; * *矩阵乘法的应用之一(国家队论文): *矩阵乘法不满足交换律,矩阵乘法满足结合律; *给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值; *把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j; *令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点); *类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数; *同理,如果要求经过k步的路径数,只需要二分求出A^k即可; * *算法思想： *类似于快速幂的矩阵相乘的方法,只是把相乘部分改成floyd; *基于动态规划：d[i][j][k],表示点i到j有2^k条路径的最短路; *INF值很奇怪,各种数据都感觉不合适,换了很多次才过;**/#include<iostream>#include<cstring>#include<cstdlib>#include<queue>#include<cstdio>#include<climits>#include<algorithm>using namespace std;const int MAXN=222;const int MAXM=1111;//const int INF=0xfffffff;const int INF=999999999;int f[MAXM];int cnt;int map[MAXN][MAXN];int res[MAXN][MAXN],tmp[MAXN][MAXN];//res[i][j]表示i与j之间的最短路（之间有n条路），这个n是时刻变化的int N,T,S,E;void solve(int n)//就像快速幂的矩阵连乘，只是把相乘部分改成floyd{ while(n) { if(n%2)//n为奇数时,n=2^a+2^a+b,这里补上b步,后面计算2*2^a步; { for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) tmp[i][j]=INF; for(int k=1; k<=cnt; k++) for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) if(tmp[i][j]>res[i][k]+map[k][j]) tmp[i][j]=res[i][k]+map[k][j]; for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) res[i][j]=tmp[i][j]; } for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) tmp[i][j]=INF; for(int k=1; k<=cnt; k++) for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) if(tmp[i][j]>map[i][k]+map[k][j]) tmp[i][j]=map[i][k]+map[k][j]; for(int i=1; i<=cnt; i++) for(int j=1; j<=cnt; j++) map[i][j]=tmp[i][j]; n=n/2; } return;}int main(){ //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); while(~scanf("%d%d%d%d",&N,&T,&S,&E)) { for(int i=0; i<=MAXN; i++) { for(int j=0; j<=MAXN; j++) map[i][j]=INF,res[i][j]=INF; res[i][i]=0; } memset(f,0,sizeof(f)); cnt=0; int u,v,w; for(int i=1; i<=T; i++) { scanf("%d%d%d",&w,&u,&v); if(f[u]==0) { cnt++; f[u]=cnt; } if(f[v]==0) { cnt++; f[v]=cnt; } map[f[u]][f[v]]=w; map[f[v]][f[u]]=w; } solve(N); printf("%d\n",res[f[S]][f[E]]); } return 0;}