学步园

以前上网看了看，prim算法比较好理解

#include<iostream>
using namespace std;
int main()
{
 int t, n, i, j, road[501][501],add, min, max, dist[501];
 bool in[501];
 cin >> t;
 while(t--)
 {
 cin >> n;
 for(i = 1; i <= n; i++)
  for(j = 1; j <= n; j++)
   cin >> road[i][j];
   for(i = 1; i <= n; i++)
     {
     in[i] = false;
     dist[i] = 65537;
     }
     max = 0;
     in[0] = true;
     for(i = 1; i <=n; i++)
       dist[i] = road[1][i];
     for(j = 1; j <=n; j++)
       {
       min = 65537;
       for(i = 1; i <=n; i++)
        {
         if(!in[i]&&dist[i]<min)
          {
          add = i;
          min = dist[i];
          }
        }
      in[add] = true;
      for(i = 1; i <=n; i++)
        if(!in[i]&&road[add][i] < dist[i])
          dist[i] = road[add][i];
        if(max < min) max = min;
       } 
    cout << max << endl;
    if(t) cout << endl;
 }
}