@ [fujiahao7700 ](https://www.luogu.com.cn/user/999366)
```
#include<bits/stdc++.h>
using namespace std;
int mp[25]; // 储存地图
int way[25][25] ; // 储存顶点i到顶点j之间的联通关系 邻接矩阵
int n ;
int answer ; // 储存最终答案
vector<int> answer_way; // 保存路径答案
void dfs(vector<int> ve,int it,int val) // 保存路径的容器和当前顶点 val储存权值总和
{
// 因为任意一个顶点都可以是起点和终点，所以不设置递归边界，并且每次进入循环比较一次
if(val > answer)
{
answer = val;
answer_way = ve; // 更换更优解的路径和权值
}
for(int i = it + 1 ; i <= n ; i ++ )
{
if(way[it][i]){
ve.push_back(i); // 压入路径的顶点稍后再次深搜查询
dfs(ve,i,val+mp[i]);
ve.pop_back();// 不要忘记弹出，查找另外一条路径
}
}
}
int main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++ ){
cin >> mp[i];
way[0][i] = 1; // 设置可以从任意一个顶点出发
}
// 输入顶点的权值
for(int i = 1 ; i <= n - 1 ; i ++ )
{
for(int j = i + 1 ; j <= n ; j ++ )
{
cin >> way[i][j] ; // 输入n个顶点之间的关系
}
}
vector<int> ve;
dfs(ve,0,0);
for(int i = 0 ; i < answer_way.size() ; i ++ )
{
cout << answer_way[i] << " ";
}
cout << endl << answer << endl;
return 0;
}
```
by huanglihuan @ 2024-01-13 15:09:44