SPOJ KFSTB - 帮助总司令：错误答案

Question

问题陈述要求找到有向无环图中从给定源节点到目标节点的路径数。

我正在尝试使用 dfs 和 dp 进行优化来实现这一点。我已经尝试了几个代码似乎工作正常的小测试用例。我认为问题在于大型测试用例，但我不知道如何测试它们。由于路径的数量可能非常大，我们将使用模数。我的代码如下：

#include<iostream>
#include<vector>
#define MOD 1000000007
using namespace std;

typedef vector<long long int> vi;
typedef vector<vi> vii;

vii graph;
vi memo;

long long int dfs(int u, int t)
    {
        if(u==t)
            return 1;
        if((memo[u]%MOD)>0)
            return memo[u]%MOD;

        for(int i=0;i<(int)graph[u].size();i++)
        {
            long long int count = (dfs(graph[u][i], t))%MOD;
            memo[graph[u][i]] = (memo[graph[u][i]]%MOD + count%MOD)%MOD;
            cur_count = (cur_count%MOD + count%MOD)%MOD;
        }
        return cur_count%MOD;
    }

int main()
{
    int d, c, b , s, t, i, a1, a2;
    cin>>d;

    while(d--)
    {
        cin>>c>>b>>s>>t;

        graph.assign(c+1,vi());

        for(i=1;i<=b;i++)
        {
            cin>>a1>>a2;
            graph[a1].push_back(a2);
        }

        memo.assign(c+1, 0);
        memo[s] = dfs(s, t)%MOD;

        cout<<memo[s]<<endl;
    }   
    return 0;
}

在函数dfs中：元素 "i" 的数组 memo[] 用于记忆以记住从 [= 到目的地的可能路径数第 30=] 个节点。 count 变量获取当前节点被访问的路径数，即 "i" 和 cur_count 获取所有路径的总路径直接连接到节点 "u"

的节点

如果我能得到一些提示或指点，那将非常有帮助。

Link原来的问题在这里：http://www.spoj.com/problems/KFSTB/

Answer 1

正如您要的 "tips"，这里有一些：

关键字：DAG
无自循环/多边缘情况
这次不是关于 I/O 格式（Space、换行等）
为每个测试用例重新初始化！！（特别是对于像 vector<> 这样的 STL 东西）
长长
逆向思考：从目的地到起点

如果仍然卡住，请询问更多:)

SPOJ KFSTB - 帮助总司令：错误答案

SPOJ KFSTB - Help the Commander in Chief: Wrong Answer

c++

algorithm

dynamic-programming

depth-first-search