图形的Dfs提供错误答案？

Question

我有一个代表车站的图表，每个节点都有与之相关的维护成本。我想查找从一个站点到另一个站点的总维护成本，这是与每个节点相关的成本的乘积。

使用dfs，我在遍历的大多数节点上都得到了正确的答案，但是在其他一些情况下却无法给出正确的答案。这是我的代码-

int DFSUtil(int currentVertex, int finalVertex, bool visited[]){

        if(currentVertex==finalVertex){
            return cost[currentVertex];
        }

        visited[v]=true;
        int sol = cost[currentVertex];

        vector<ll>::iterator it;

        bool flag=false;

        for(it=adjcurrentVertex].begin(); it!=adj[currentVertex].end(); it++){
            flag=false;
            if(!visited[*it]){
                sol *= DFSUtil(*it,finalVertex,visited);
                flag=true;
            }
        }
        if(!flag){
            sol /= cost[currentVertex];
        }
        return sol;
    }

cost array包含每个顶点的相关成本。有人可以帮忙吗？在某些情况下，这给了我正确的答案，但并非在每个人中都给了我正确答案。假设我有5个节点-1 2 3 4 5，成本为2 6 4 3 5，节点1连接到节点2和3，节点2连接到4和5。那么从节点4开始的维护成本到5必须为3 * 6 * 5 = 90，但代码为180。

Answer 1

您将包括从所有连接到路径上节点的成本，而不仅仅是路径上的成本。

[使用示例数据，当您以currentVertex等于2评估成本时，将顶点1和顶点5的成本相乘。由于顶点1不在路径上，并且成本为2，所以最终成本是预期的两倍。