http://acm.hdu.edu.cn/showproblem.php?pid=2807
第一次做矩阵乘法,没有优化超时,看了别人的优化的矩阵乘法,就过了。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 100
using namespace std;
const int inf=<<; int n,m,t1,x,y;
int g[maxn][maxn];
int d[maxn][maxn];
int aa[maxn][maxn][maxn]; void deal(int a,int b)
{
for(int i=; i<=m; i++)
{
d[][i]=;
for(int j=; j<=m; j++)
{
d[][i]+=(aa[a][i][j]*d[b][j]);
}
}
for(int i=; i<=n; i++)
{
if(i==a||i==b) continue;
bool flag=false;
for(int k=; k<=m; k++)
{
if(d[][k]!=d[i][k])
{
flag=true;
break;
}
}
if(!flag) g[a][i]=;
}
} int main()
{
while(cin>>n>>m)
{
if(n==&&m==) break;
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
d[i][j]=;
for(int k=; k<=m; k++)
{
scanf("%d",&aa[i][j][k]);
d[i][j]+=(aa[i][j][k]*k);
}
}
}
for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
g[i][j]=g[j][i]=inf;
}
}
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(i==j) continue;
deal(i,j);
}
}
for(int k=; k<=n; k++)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
if(g[i][j]>g[i][k]+g[k][j])
{
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
scanf("%d",&t1);
for(int i=; i<t1; i++)
{
scanf("%d%d",&x,&y);
if(g[x][y]!=inf) printf("%d\n",g[x][y]);
else printf("Sorry\n");
}
}
return ;
}