记录编号	511988	评测结果	AAAAAAAAAA
题目名称	[NOIP 2017]逛公园	最终得分	100
用户昵称	サイタマ	是否通过	通过
代码语言	C++	运行时间	1.878 s
提交时间	2018-10-01 09:21:36	内存使用	114.75 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
class EDGE
{public:
    int u, v, w, next;
}edge[400010], redge[400010];
bool vis[400010], used[400010][51], flag;
int T, n, m, k, p, a, b, c, head[400010], rhead[400010], cnt, rcnt, d[400010], f[400010][51], ans;
void ADDE(int u, int v, int w)
{
    edge[++cnt] = {u, v, w, head[u]};
    head[u] = cnt;
}
void RADDE(int u, int v, int w)
{
    redge[++rcnt] = {u, v, w, rhead[u]};
    rhead[u] = rcnt;
}
void SPFA()
{
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(1);
    d[1] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                if(!vis[v])
				{
                	q.push(v);
                	vis[v] = 1;
                }
            }
        }
    }
}
int dfs(int u, int rest)
{
    if(!flag) return 0;
    if(~f[u][rest]) return f[u][rest];
    used[u][rest] = 1;
    f[u][rest] = 0;
    for(int i = rhead[u]; i; i = redge[i].next)
    {

        int v = redge[i].v;
        int w = redge[i].w;
        int nowrest = d[u] - d[v] + rest - w;
        if(nowrest < 0)continue;
        if(used[v][nowrest])
        {
            flag = 0;
            return 0;
        }
        f[u][rest] = (f[u][rest] + dfs(v, nowrest)) % p;
    }
    used[u][rest] = 0;
    return f[u][rest];
}
int main()
{
    freopen("2017park.in", "r", stdin);
    freopen("2017park.out", "w", stdout);
    scanf("%d", &T);
    while(T --)
    {
        cnt = 0;
        rcnt = 0;
        ans = 0;
        flag = 1;
        memset(head, 0, sizeof(head));
        memset(rhead, 0, sizeof(rhead));
        memset(d, 0x7f, sizeof(d));
        memset(used, 0, sizeof(used));
        memset(f, -1, sizeof(f));
        scanf("%d%d%d%d", &n, &m, &k, &p);
        for(int i = 1; i <= m; ++ i)
        {
            scanf("%d%d%d", &a, &b, &c);
            ADDE(a, b, c);
            RADDE(b, a, c);
        }
        SPFA();
        f[1][0] = 1;
        for(int i = 0; i <= k && flag; ++ i)
            ans = (ans + dfs(n, i)) % p;
        if(!flag)
            ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}