http://acm.hdu.edu.cn/showproblem.php?pid=2807常規矩陣比較復雜度是O(n^2), 我們可把2維的數組乘以一個一維數組 來比較
通過這道題的測試，效果灰常讓人吃驚。。。
常規比較的代碼用C++提交超時，但是G++可以過掉，1484MS
#include <iostream>
using namespace std;
#define N 81
#define INF 99999999
int map[N][N], n, m;
struct node{
int Map[N][N];
} rec[N];
struct nnode{
int Map[N];
}recone[N];
void cmp(int a, int x)
{
int i;
for (i=1; i<=m; i++)
if (recone[x].Map[i] != recone[0].Map[i])
return;
map[a][x] = 1;
}
void creat(int a, int b)
{
int i, j, k, s;
for (i=1; i<=m; i++)
{
recone[0].Map[i] = 0;
for (j=1; j<=m; j++)
{
recone[0].Map[i] += rec[a].Map[i][j] * recone[b].Map[j];
}
}
for (i=1; i<=n; i++)
if (i != a && i != b)
cmp(a, i); //判斷 a 與 i的關系
}
int main()
{
int i, j, k;
while (scanf("%d %d", &n, &m), n+m)
{
for (i=1; i<=n; i++)
for (map[i][i]=0, j=i+1; j<=n; j++)
map[i][j] = map[j][i] = INF; //初始化矩陣之間關系
for (k=1; k<=n; k++)
{
for (i=1; i<=m; i++)
{
recone[k].Map[i] = 0;
for (j=1; j<=m; j++)
{
scanf("%d", &rec[k].Map[i][j]);
recone[k].Map[i] += rec[k].Map[i][j] * j; // 2->1
}
}
} // 接受矩陣信息
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i != j)
creat(i, j); // 處理矩陣 i*j
for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (map[i][k] + map[k][j] < map[i][j])
map[i][j] = map[i][k] +map[k][j];
scanf("%d", &m);
while (m--)
{
scanf("%d %d", &i, &j);
if (map[i][j] != INF)
printf("%d\n", map[i][j]);
else
printf("Sorry\n");
}
}
return 0;
}
posted on 2009-12-04 09:05
西風蕭瑟 閱讀(2220)
評論(12) 編輯 收藏 引用 所屬分類:
圖論