首页 > ACM题库 > HDU-杭电 > HDU 2807-The Shortest Path-最短路径[解题报告]HOJ
2014
02-17

HDU 2807-The Shortest Path-最短路径[解题报告]HOJ

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)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮