动态规划题，状态转移方程为 dp[i] = max(dp[i], dp[j] + map[j][i])，dp 保存到达此城市的最大魅力值，j 是可以到达 i 的城市。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;int map[MAXN][MAXN]; //景点之间的通路
int price[MAXN]; //景点的魅力值
int pre[MAXN]; //前一个城市，pre[i]表示目前路线上i城市的前一个是j城市
int dp[MAXN]; //动态规划数组，dp[i]表示从起点到达i城市的最大魅力值//递归从前到后输出
void output(int x)
{if (x == -1)return;output(pre[x]);cout << x << "->";
}int main()
{int T;cin >> T;int n, m;int count = 1; //测试用例数while (T--){cin >> n;for (int i = 1; i <= n; ++i){cin >> price[i];}price[n + 1] = 0; //起点作为终点时没有魅力值pre[1] = -1; //起点没有前向城市memset(dp, 0, sizeof(dp));memset(map, -1, sizeof(map));cin >> m;int i, j, k;for (k = 1; k <= m; ++k){cin >> i >> j;map[i][j] = price[j]; //将到达城市的魅力值作为路线的魅力值}for (int i = 1; i <= n + 1; i++) //动态规划{for (int j = 1; j < i; j++){if (map[j][i] != -1 && dp[j] + map[j][i] > dp[i]){dp[i] = dp[j] + map[j][i];pre[i] = j;}}}if (count > 1)cout << endl;cout << "CASE " << count++ << "#" << endl;cout << "points : " << dp[n + 1] << endl;cout << "circuit : ";output(pre[n + 1]);cout << 1 << endl;}return 0;
}
继续加油。