c++ - SPOJ KFSTB - 帮助总司令 : Wrong Answer

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[] 用于内存，以记住从第“i”个节点到目的地的可能路径数。 count 变量获取当前节点被访问的路径数，即“i”和cur_count 获取直接连接到节点“u”的所有节点的总路径

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

原始问题的链接在这里:http://www.spoj.com/problems/KFSTB/

Answer 1

当你要求一些“提示”时，这里有一些:

1. 关键词:DAG
2. 无自循环/多边缘情况
3. 这次不是关于 I/O 格式(空格、换行等)
4. 为每个测试用例重新初始化!! (特别是对于像 vector<> 这样的 STL 东西)
5. 龙龙
6. 逆向思考:从目的地到起点

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