tsp问题c++代码
时间: 2023-08-10 22:07:18 浏览: 53
以下是一个使用贪心算法的TSP问题的C++代码示例:
```c++
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dist[N][N];
int n,vis[N],ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>dist[i][j];
memset(vis,0,sizeof(vis));
vis[1]=1;
int pre=1;
for(int i=1;i<n;i++)
{
int minn=1e9,pos=0;
for(int j=1;j<=n;j++)
{
if(vis[j]==0&&dist[pre][j]<minn)
{
minn=dist[pre][j];
pos=j;
}
}
vis[pos]=1;
ans+=minn;
pre=pos;
}
ans+=dist[pre][1];
cout<<ans<<endl;
return 0;
}
```
该代码中, `dist` 数组存储了城市之间的距离。在贪心算法中,我们从城市1开始,每次选择与当前城市距离最近的未访问城市,直到所有城市都访问过。最后,我们将最后一个城市与城市1相连,计算总路程并输出。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)