阿里算法工程师笔试题
答案如下:
#include <iostream>
#include <limits.h>
using namespace std;
int F[100][100];
int minStep = INT_MAX;
void dfs(int **array, int N, int i, int j, int M, int sum)
{
if ((i == j)&&(M == 0))
{
if (sum <= minStep)
{
minStep = sum;
}
return;
}
if (M < 0)
{
return;
}
for (int k = 0; k < N; k++)
{
if (k != i)
{
sum = sum + array[i][k];
M--;
dfs(array, N, k, j, M, sum);
sum = sum - array[i][k];
M++;
}
}
}
int main()
{
int N;
int M;
while (cin >> N >> M)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
F[i][j] = INT_MAX;
}
}
int **array = new int*[N];
for (int i = 0; i < N; i++)
{
array[i] = new int[N];
for (int j = 0; j < N; j++)
{
int tem;
cin >> tem;
array[i][j] = tem;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
minStep = INT_MAX;
dfs(array, N, i, j, M, 0);
F[i][j] = minStep;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N - 1; j++)
{
cout << F[i][j] << " ";
}
cout << F[i][N - 1] << endl;
}
}
system("pause");
}