回溯 part1 【8-】

leetcode2065最大化一张图中的路径价值

很难的一道题了，难的在于对 路径的处理；

看了答案，略懂，还是先记录一下。

 题目还是挺好理解的，思路其实也很明确，但是edges 数组 如何处理遍历的数组元素想不出来。

下面是leetcode给的答案，自己补了一下完整代码 通过调试 帮助理解

#include
#include
using namespace std;
int ans = 0;
int n, m;
int maxTime;
void dfs(int u, int time, int value, vector &visited, vector>> &g, vector& values) {
    if (u == 0) {
        ans = max(ans, value);
    }
       
    for (int j = 0; j < g[u].size(); j++)
    {
        int v = g[u][j].first;
        int dist = g[u][j].second;
        if (time + dist <= maxTime) {
        if (!visited[v]) {
        visited[v] = true;
        dfs(v, time + dist, value + values[v], visited, g, values);
            visited[v] = false;
         }
        else {
           dfs(v, time + dist, value, visited, g, values);
             }
         }
     }
}
int maximalPathQuality(vector& values, vector>& edges, int maxTime) {
    int n = values.size();
    vector>> g(n);
    for (const auto& edge : edges) {
        g[edge[0]].emplace_back(edge[1], edge[2]);
        g[edge[1]].emplace_back(edge[0], edge[2]);
    }
    vector visited(n);
    visited[0] = true;
    dfs(0, 0, values[0],visited,g,values);
    return ans;
}
int main()
{
	cin >> n>>m>>maxTime;
    vectorvalues(n,0);
	vector>edges(m,vector(m,0));
    for (int i = 0; i < n; i++)
        cin >> values[i];
	for (int i = 0; i < m; i++)
	{
		for(int j=0;j> edges[i][j];
	}
    maximalPathQuality(values, edges, maxTime);
    cout << ans;
	return 0;
}

但是 有个写法，VS报错了：

for (const auto& [v, dist]: g[u]) {}

于是换成了

for (int j = 0; j < g[u].size(); j++){}

g是用来存放路径和花费时间的，g[u]打印结果如下：

g[0] :  [1 10]  [3 10]

g[1] :  [0 10]  [2 15]

g[2] :  [1 15]

g[3] :  [0 10]

每一行中的每一个数组的第一个数 都是将 该u中的结点所连接的 下一个结点表示出来。

其中 g[u]中的 u 就表示 结点此时的数值。

u为0 表示起点 或者回到起点。 

不太懂，期望下次重刷的时候能理解更深一点。