kritak's blog

By kritak, history, 3 years ago, In English

SPOJ-KFSTB

I am using dp with dfs to calculate the number of paths to each point. Can somebody tell me what am I missing?

const int mod = 1e9 + 7;

void solve () {

int C, B, S, T;
cin >> C >> B >> S >> T;

vector<ll> graph[C + 1];
vector<bool> vis(C + 1);

for (int i = 0; i < B; i++) {
    ll x, y;
    cin >> x >> y;
    graph[x].push_back(y);
}

vector<ll> dp(C + 1);
dp[S] = 1LL;
stack<ll> st;
st.push(S);

while (!st.empty()) {
    ll v = st.top();
    st.pop();
    vis[v] = true;

    for (ll u: graph[v]) {
        dp[u] = (dp[u] + dp[v]) % mod;
        if (!vis[u])
            st.push(u);
    }
}

cout << dp[T] % mod << "\n";

}

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;
while (t--) {
    solve();
}

}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it