I'm working on a algorithm problem, and it discribed as follows:
Suppose the deep learning model is a directed acyclic graph. If operator A depends on the output of operator B, then A can be calculated after the execution of B. If there is no dependency relation, then A can be executed in parallel. Given N nodes, the information of each node contains the execution time of the node and the list of the next nodes, and the shortest execution time of the neural network is calculated. The node index starts at 0.
and here is the input example:
7
A 10 1 2 3
B 9 4 5 6
C 22
D 20
E 19
F 18
G 21
Here is my solution:
#include <bits/stdc++.h>
using namespace std;
int dfs(int nodeTime, const vector<int>& nextNodes, vector<vector<int>> NN){
// Check whether the children of the current node have children
bool is_end = true;
for (int node : nextNodes) {
if (NN[node][1] != 0){
is_end = false;
break;
}
}
//The children of the current node have no children, find the maxTime
if (is_end) {
int maxTime = 0;
for (int node : nextNodes) {
maxTime = max(node, maxTime);
}
return nodeTime + maxTime;
}
//some children of the current node have children, keep doing dfs()
else{
int maxTime = 0;
for (int nodeIdx : nextNodes) {
if (NN[nodeIdx].size() != 1){
vector<int> next;
next.assign(NN[nodeIdx].begin() + 1, NN[nodeIdx].end());
maxTime = max(maxTime, dfs(NN[nodeIdx][0], next, NN));
}
else maxTime = max(maxTime, NN[nodeIdx][0]);
}
return maxTime + nodeTime;
}
}
int str_int(const string& s){
char c[10];
strcpy(c, s.c_str());
return atoi(c);
}
int main() {
// input stage
int n;
cin >> n;
vector<vector<int>> NN;
vector<int> temp;
vector<string> stemp;
string s;
for (int i = 0; i < n; ++i) {
stemp.clear();
temp.clear();
while (cin >> s){
stemp.push_back(s);
if (getchar() == '\n') break;
}
for (int j = 1; j < stemp.size(); ++j) {
temp.push_back(str_int(stemp[j]));
}
NN.push_back(temp);
}
vector<int> initialNextNodes; //Initialize the sequence of children of the starting node
initialNextNodes.assign(NN[0].begin() + 1, NN[0].end());
int res = dfs(NN[0][0], initialNextNodes, NN);
cout << res;
return 0;
}
The right output is 40
, Debug mode gives the right answer, but Run mode gives the wrong answer, I can't figure out what went wrong. I looked up the common causes of this error, probably a pointer being used without space allocated, or a variable being used without an initial value assigned. But these do not seem to be the answer to my question, can anyone help me? I would be so grateful.