The Shortest Path
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2440 Accepted Submission(s): 784
Problem Description
There are N cities in the country. Each city is represent by a matrix size of M*M. If city A, B and C satisfy that A*B = C, we say that there is a road from A to C with distance 1 (but that does not means there is a road from C to A). Now the king of the country wants to ask me some problems, in the format: Is there is a road from city X to Y? I have to answer the questions quickly, can you help me?
Input
Each test case contains a single integer N, M, indicating the number of cities in the country and the size of each city. The next following N blocks each block stands for a matrix size of M*M. Then a integer K means the number of questions the king will ask, the following K lines each contains two integers X, Y(1-based).The input is terminated by a set starting with N = M = 0. All integers are in the range [0, 80].
Output
For each test case, you should output one line for each question the king asked, if there is a road from city X to Y? Output the shortest distance from X to Y. If not, output "Sorry".
Sample Input
3 2 1 1 2 2 1 1 1 1 2 2 4 4 1 1 3 3 2 1 1 2 2 1 1 1 1 2 2 4 3 1 1 3 0 0
Sample Output
1 Sorry
Source
题目很清楚：
如果满足A*B=C 那么就说A到C是联通的....
反之则为不连通...
这里需要用到的求最短路径，对于稠密图的，用弗洛伊德算法比狄斯喹诺算法要好一点。
至于要优化，看来结题报告之后，觉得还是不大靠谱，就没有写，写的是一个朴素的矩阵相乘算法+floyd算法
代码：
1 #include2 #include 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 6 const int maxn=82; 7 int arr[maxn][maxn][maxn]; 8 int ans[maxn][maxn]; 9 int tem[maxn][maxn]; 10 11 int n,m,w; 12 13 void init(int a[][maxn]) 14 { 15 for(int i=1;i<=n;i++) //城市初始化 16 { 17 for(int j=1;j<=n;j++) 18 { 19 if(i==j)a[i][j]=0; 20 else a[i][j]=inf; 21 } 22 } 23 } 24 25 void floyd(int a[][maxn]) //运用floyd算法求城市间的最短路径 26 { 27 for(int k=1;k<=n;k++) 28 { 29 for(int i=1;i<=n;i++) 30 { 31 for(int j=1;j<=n;j++) 32 { 33 if(ans[i][j]>ans[i][k]+ans[k][j]) 34 ans[i][j]=ans[i][k]+ans[k][j]; 35 } 36 } 37 } 38 } 39 40 void Matrix(int a[][maxn],int p1,int p2) 41 { 42 for(int i=1;i<=m;i++) 43 { 44 for(int j=1;j<=m;j++) 45 { 46 a[i][j]=0; // init() 47 for(int k=1;k<=m;k++) 48 { 49 a[i][j]+=arr[p1][i][k]*arr[p2][k][j]; 50 } 51 } 52 } 53 } 54 55 void work() 56 { 57 int t1,t2,t3; 58 for(int i=1;i<=n;i++) 59 { 60 for(int j=1;j<=n;j++) 61 { 62 if(i==j) continue; //a，b 两数组不能相同 63 Matrix(tem,i,j); //两个矩阵相乘 64 for(t1=1;t1<=n;t1++) 65 { 66 //a，b,c三数组不能相同 67 if(t1!=i&&t1!=j) 68 { 69 for( t2=1;t2<=m;t2++) 70 { 71 for(t3=1;t3<=m;t3++) 72 { 73 //得到的结果相比较 74 if(tem[t2][t3]!=arr[t1][t2][t3]) 75 goto loop; 76 } 77 } 78 loop: 79 if(t3>m) 80 ans[i][t1]=1; 81 } 82 } 83 } 84 } 85 } 86 87 int main() 88 { 89 int a,b; 90 while(scanf("%d%d",&n,&m)&&n+m!=0) 91 { 92 for(int i=1;i<=n;i++) 93 for(int j=1;j<=m;j++) 94 for(int k=1;k<=m;k++) 95 scanf("%d",&arr[i][j][k]); 96 init(ans); 97 work(); 98 floyd(ans); 99 scanf("%d",&w);100 while(w--)101 {102 scanf("%d%d",&a,&b);103 if(ans[a][b]==inf)104 printf("Sorry\n");105 else106 printf("%d\n",ans[a][b]);107 }108 }109 return 0;110 }