using namespace std;
int arr[1000][1000];
int dist[1000][1000];
int main()
{
int N,M,count;
count = 0;
cin >> N;
for (int i = 0;i < N; i++)
{
cin >> M;
count = 0;
for (int a = 0;a < M; a++)
{
for (int b = 0;b < M; b++)
{
cin >> arr[a][b];
}
}
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
{
if (arr[i][j] == 1)
dist[i][j] = 1;
else
dist[i][j] = 999999999;
}
for (int i = 0; i < M; i++)
{
for (int k = 0; k < M; k++)
{
for (int j = 0; j < M; j++)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
cout << dist[0][M - 1]<<endl;
}
return 0;
}
沒有留言:
張貼留言