2014
02-17

# The Shortest Path

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?

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].

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].

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

1
Sorry

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define FF(i, n) for(int i = 0; i < n; i++)
#define M 85
#define inf 0x3fffffff

int n;

struct mat{
int x[M][M];
friend bool operator == (const mat &a, const mat &b)
{
FF(i, n) FF(j, n)
if (a.x[i][j] != b.x[i][j])
return false;
return true;
}
}p[M];

mat matmul(const mat &a, const mat &b)
{
mat tp;
FF(i, n) FF(j, n) tp.x[i][j] = 0;
FF(i, n) FF(k, n) if(a.x[i][k]) FF(j, n) if(b.x[k][j])
tp.x[i][j] += a.x[i][k]*b.x[j][k];
return tp;
}

int dis[M][M], m;

void floyd()
{
FF(i, m) FF(j, m) dis[i][j] = inf;
FF(i, m) FF(j, m) if (i != j)
{
mat o = matmul(p[i], p[j]);
FF(k, m) if (i != k && k != j && o == p[k]) dis[i][k] = 1;
}
FF(k, m) FF(i, m) FF(j, m)
{
if (dis[i][k] == inf || dis[k][j] == inf) continue;
int tp = dis[i][k] + dis[k][j];
if (tp < dis[i][j]) dis[i][j] = tp;
}
}

int main()
{
int t, x, y;
while (scanf("%d%d", &m, &n), (m||n))
{
FF(i, m) FF(j, n) FF(k, n) scanf("%d", &p[i].x[j][k]);
floyd();
scanf("%d", &t);
while (t--)
{
scanf ("%d%d", &x, &y);
--x; --y;
if (dis[x][y] == inf) puts("Sorry");
else printf("%d\n", dis[x][y]);
}
}
return 0;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮