MST算法求满足三角不等式的TSP问题的C++代码

以下是使用Prim算法求解满足三角不等式的TSP问题的C++代码：

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int maxn=1005;

int n,cnt;
int dis[maxn][maxn],lowc[maxn];
bool vis[maxn];

void prim()
{
    memset(vis,false,sizeof(vis));
    vis[1]=true;
    for(int i=2;i<=n;i++)
        lowc[i]=dis[1][i];
    for(int i=2;i<=n;i++)
    {
        int p,minn=INF;
        for(int j=2;j<=n;j++)
            if(!vis[j]&&minn>lowc[j])
            {
                minn=lowc[j];
                p=j;
            }
        cnt+=minn;
        vis[p]=true;
        for(int j=2;j<=n;j++)
            if(!vis[j]&&lowc[j]>dis[p][j])
                lowc[j]=dis[p][j];
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>dis[i][j];
    prim();
    cout<<cnt<<endl;
    return 0;
}

其中，dis[i][j]表示点i到点j的距离，cnt表示最小生成树的权值和。