I sent the code, I tried my best looking for the error (I spent more than 2 hours on this), I wrote out what I am getting wrong, so why are you sending me that link when I followed the guidelines?
Well in my code it is somewhat obvious that the main of the code is just inputting all the data, and the dfs function is probably where it went wrong, I’m just unsure of why because it seems all correct to me. Idk, I just started DFS.
If you want to know why your program is printing “2 0,” it’s because your program is incorrect.
If you want to know how your program is printing “2 0,” you should print out the variables at every step of the recursive function and verify that it matches what you get when you simulate your program by hand.
If you want to know why your program is incorrect, @SansPapyrus683 has pointed out one of the reasons above.
I’ve updated the link that @SansPapyrus683 sent above accordingly. Hope it helps!
By the way, when I run the code, I get “2 2,” not “2 0.”
Sorry if this is a little messy, I’m tired rn so I can’t really concentrate.
As @SansPapyrus683 said, for each query, the visited array must be reset.
This is because each query is independent of the other.
Another problem I found while tracing through your code:
For the DFS, instead of dfs(visited[i], des, len+a[cur][i]);.
You should be using dfs(i, des, len + a[cur][i]);
This is because your dfs has parameters. (current node, destination node, current cost).
And so accordingly, when you dfs , you should be passing in the next node.
I hope this was helpful and made sense.
Your code after those changes: it has the right output, 2 7 .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
#define space " "
#define sz(x) (int)(x).size()
#define MOD 100007
void setIO(string name = "") {
/*if (sz(name)) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}*/
}
int n, q;
int a[1005][1005];
int visited[1005];
bool found;
int ans = 0;
void dfs(int cur, int des, int len) {
if (found == true) {
return;
}
// destination reached
if (cur == des) {
ans = len;
found = true;
return;
}
// loop through possible choices of next node in dfs.
for (int i = 0; i < n; i++) {
if (a[cur][i] != 0 && visited[i] == 0) {
visited[i] = 1;
// [CHANGE 1: error that i found: the 1st value in the dfs should be 'i', not 'visited[i]'.]
dfs(i, des, len + a[cur][i]);
visited[i] = 0;
}
}
}
int main() {
//setIO("");
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
// initialize matrices
for (int i = 0; i < n + 1; i++) {
visited[i] = 0;
for (int j = 0; j < n + 1; j++) {
a[i][j] = 0;
}
}
// read edges
for (int i = 0; i < n - 1; i++) {
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
t1--;
t2--;
a[t1][t2] = t3;
a[t2][t1] = t3;
}
// process queries
for (int i = 0; i < q; i++) {
//[CHANGE 2]: each query is independent, so visited array must be reset every time.]
fill(visited, visited + n, 0);
int b, c;
cin >> b >> c;
b--; c--;
ans = 0;
found = false;
visited[b] = 1;
dfs(b, c, 0);
cout << "ANSWER: "<< ans << endl;
}
}
