题解 | #相遇#

dfs+打表

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

int MOD_NUM = 100007;

int dfs(vector<vector<int>>& A, vector<int>& ans, vector<bool>& vis, int node, int des){
    if(vis[node]) return ans[node];
    if(node==des) return 1;
    vis[node] = true;
    int tmp = 0;
    for(int i=0;i<A[node].size();i++){
        tmp+=dfs(A, ans, vis, A[node][i], des);
        tmp = tmp%MOD_NUM;
    }
    ans[node] = tmp%MOD_NUM;
    return ans[node];
}

int main() {
    int n,m,t;
    cin>>n>>m>>t;
    vector<bool> vis(n);
    vector<int> ans(n);
    vector<vector<int>> A(n);
    while(m!=0){
        m--;
        int x,y;
        cin>> x>>y;
        A[x-1].push_back(y-1);
    }
    int q;
    cin >> q;
    while(q!=0){
        q--;
        int s;
        cin>> s;
        int ret = dfs(A, ans, vis, s-1, t-1);
        cout << ret <<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")