Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
13
Indexable
Never
#include <fstream>
#include <climits>
#include <iostream>
using namespace std;
ifstream fin ("prim.in");
ofstream fout ("prim.out");

const int nMAX = 100;

int n, m;
int mc[nMAX + 1][nMAX + 1];
int arb[nMAX + 1], arbcost;

void prim(int nod)
{
   int i, j, mini, minj, mincost, k;
   for (i = 1; i <= n; ++i)
      arb[i] = -1;
   arb[nod] = 0;
   arbcost = 0;

   for (k = 1; k <= n-1; ++k)
   {
      mincost = INT_MAX/2;

      for (i = 1; i <= n; ++i)
         for (j = 1; j <= n; ++j)
         {
            if (arb[i] != -1 && arb[j] == -1 && mc[i][j] != 0)
               if (mc[i][j] < mincost)
               {
                  mincost = mc[i][j];
                  mini = i;
                  minj = j;
               }
         }

      if (mincost != INT_MAX/2)
      {
         arbcost += mincost;
         arb[minj] = mini;
      }
   }
}


int main()
{
   int i, j, c, k, plecare;
   fin >> n >> m;

   for (k = 1; k <= m; ++k)
   {
      fin >> i >> j >> c;
      mc[i][j] = mc[j][i] = c;
   }
    cin >> plecare;
   prim(plecare);

   fout << arbcost << '\n';
   for (k = 1; k <= n; ++k)
      fout << arb[k] << ' ';
}