学步园

prim算法

#include <iostream>
using namespace std;
int m[101][101];
int prim(int k){
    int ans = 0, dist[101];
    bool vis[101];
    for(int i = 1; i < k; i++){
        dist[i] = m[0][i];
        vis[i] = 0;
    }
    vis[0] = true;
    int cnt = k-1;
    while(cnt--){
        int mi = 9999999;
        int tmp = 0;
        for(int i = 1; i < k; i++)
            if(dist[i] < mi && vis[i] == 0){
                mi = dist[i];
                tmp = i;
        }
        ans += mi;
        vis[tmp] = true;
        for(int i = 0; i < k; i++)
            if(m[tmp][i] < dist[i] && vis[i] == 0)
                dist[i] = m[tmp][i];
            cout << ans  << endl;
    }
    return ans;
}
int main(int argc, char const *argv[])
{
    int n;
    while(cin >> n){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> m[i][j];
       cout << prim(n) << endl;
    }
    return 0;
}