USACO Pasture Walking

This is a rather old problem, but the link is here: here

This problem uses DFS and the code I have right now is this:

#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;
    }
    if(cur == des){
        ans = len;
        found = true;
        return;
    }
    for(int i = 0; i < n; i++){
        if(a[cur][i] != 0 && visited[i] == 0){
            visited[i] = 1;
            dfs(visited[i], des, len+a[cur][i]);
            visited[i] = 0;
        }
    }
}

int main() {
	//setIO("");
	cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for(int i = 0; i < n+1; i++){
        visited[i] = 0;
        for(int j = 0; j < n+1; j++){
            a[i][j] = 0;
        }
    }
    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;
    }
    for(int i = 0; i < q; i++){
        int b, c;
        cin >> b >> c;
        b--; c--;
        ans = 0;
        found = false;
        visited[b] = 1;
        dfs(b, c, 0);
        cout << ans << endl;
    }
}

I am not passing the example test case and am only get “2 0” as my output instead of “2 7”, does anyone know why?

https://forum.usaco.guide/t/how-to-ask-for-help-on-a-problem/338/2

2 Likes

I don’t get why you even sent me that link.

  1. I did read the guidelines
  2. 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?

So do you want me to try to figure out the code without any comments, or…?

1 Like

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.

Is not resetting the visited array for each query intended behavior?

1 Like
  • 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.”

2 Likes

It does reset the visited array, right? Because once done with the dfs it sets the visited to 0 instead of 1. 0 means not visited and 1 means visited.

Sorry if this is a little messy, I’m tired rn so I can’t really concentrate.

  1. As @SansPapyrus683 said, for each query, the visited array must be reset.
    This is because each query is independent of the other.

  2. 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. :slight_smile:

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;
    }
}
1 Like

Thanks for your suggestions, really appreciate them. Thanks for the help!

1 Like