john农场问题

/*

Description 

John是一个农场主，他有几个牧场，为了好好照顾他的牛，他必须在几个牧场之间来回，可糟糕的天气往往使得道路非常泥泞，为此John准备在牧场之间铺一些石子路，这样在下雨天也能快速地从一个牧场到另外一个牧场。但John的资金有限，为了自己能从任一个牧场都通过石子路到达另外一个牧场，他需要好好设计一下线路。请帮助John设计好线路，使得John能从任一个牧场都通过石子路到达另外一个牧场，且线路的费用最低。

输入：

第一行是一个整数K，表示有多少个测试用例，以后每个测试用例占n+1行。每个测试用例的第一行为一个整数n（3<=n<=20），表示有多少个牧场，从第二行开始为一个n*n的矩阵，矩阵元素aij表示从i个牧场到j个牧场的铺路费用。

输出：

每行输出一个测试用例的最小铺路费用。

 

  

Sample Input  

2

6

0 6 1 5 0 0

6 0 5 0 3 0

1 5 0 5 6 4

5 0 5 0 0 2

0 3 6 0 0 6

0 0 4 2 6 0

4

0 1 2 3

1 0 3 4

2 3 0 1

3 4 1 0 

  

Sample Output  

15

4 

*/

# include <stdio.h>


int findMinimumCost(int input[21][21],int n);//这里[][]必须有下标

int main(void)
{
    int cases,n,i,j,input[21][21],minimumCost;

    scanf("%d",&cases);

    while(cases--)
    {
        scanf("%d",&n);

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&input[i][j]);
                    if( 0 == input[i][j] )
                    {
                        input[i][j] = 9999999;
                    }
            }
        }

        minimumCost = findMinimumCost(input,n);
        printf("%d\n",minimumCost);
    }

    return 0;
}

int findMinimumCost(int input[21][21],int n)
{
    bool mark[21];
    int k,j,m,lowestCost[21],minimumCost,min;

    minimumCost = 0;
    mark[1] = true;

    for(k=2;k<=n;k++)
    {
        lowestCost[k] = input[1][k];
        mark[k] = false;
    }

    for(k=1;k<n;k++)
    {
        min = 9999999;
        j = 1;

        for(m=2;m<=n;m++)
        {
            if( lowestCost[m] < min && !mark[m] )
            {
                min = lowestCost[m];
                j = m;
            }
        }
        mark[j] = true;
        minimumCost += min;

        for(m=2;m<=n;m++)
        {
            if( input[j][m] < lowestCost[m] && !mark[m] )
            {
                lowestCost[m] = input[j][m];
            }
        }
    }

    return minimumCost;


}