题解 P3953 【逛公园】

· · 题解

感觉是个暴力0 0

考虑如果不存在0环怎么做。

稍微思考一下可以想出状态。

设f[x][vib]为到x点时与从起点开始的最短路的偏移量为vib的时候的总方案数目。

怎么转移？spfa？不行，因为它要推入队列的是拆点后的f'[x][vib]与f[x][vib]的差，即它增加了多少，这样的话就退化成了暴力了。

拓扑排序。

那么直接从1开始更新f数组，按照拓扑序枚举偏移量转移就行了。

但是实际上并不用这么做，我们枚举最后总的偏移量，然后记忆化搜索就行了。

但是这样真的对么？

你是不是忘了考虑它有的点不能到n0 0，所以在算偏移量的时候依据从起点开始的最短路是不对的。

那这怎么办？

我们把边反过来，从n开始最短路，按照这个最短路来算偏移量就行了。

正确性自己想想应该是对的。

最后我们看0环。

那只要看(x, vib)这个状态是否被访问了两次就好了嘛。

// shuddering in a technicolour beat
// caught up shivering
# include <bits/stdc++.h>

using namespace std;

# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0;
    while(ch < '0' || ch > '9') ch = gc();
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return ret;
}

# define RG register
# define REP(i, a, b) for(RG int i = a; i <= b; ++ i)
# define REPD(i, a, b) for(RG int i = a; i >= b; -- i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, h, x, e) for(RG int i = h[x]; ~i; i = e[i].next)
# define STOP system("pause")
# define QAQ puts("*")

const int N = 1e5 + 5, K = 50 + 5;

int n, m, k, MOD;
int cnt, cntr, head[N], revh[N];
struct qwq { int v, next, c; } edge[N << 1], reve[N << 1];
inline void add(int u, int v, int c) { edge[++ cnt] = (qwq) { v, head[u], c }, head[u] = cnt; }
inline void addr(int u, int v, int c) { reve[++ cntr] = (qwq) { v, revh[u], c}, revh[u] = cntr; }
inline void inc(int &a, int b) { a = (a + b) % MOD; }

const int B = N - 3;

int d[N], vd[N][K];
queue<int> Q;
bool vis[N], flag; 
void spfa(int S) {
    CLR(d, 0x3f); // CLR(vis, 0);
    vis[S] = 1;
    Q.push(S); 
    d[S] = 0;
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        REPG(i, revh, x, reve) {
            int v = reve[i].v, c = reve[i].c;
            if(d[x] + c < d[v]) {
                d[v] = d[x] + c;
                if(!vis[v]) { 
                    Q.push(v), vis[v] = 1;
                }
            }
        }
        vis[x] = 0;
    }
}
int f[N][K];
int dfs(int x, int vib) {
    if(vd[x][vib]) { flag = 1; return 0; }
    if(~f[x][vib]) return f[x][vib];
    vd[x][vib] = 1;
    int ret = 0;
    REPG(i, head, x, edge) {
        int v = edge[i].v;
        int tmp = vib - (d[v] + edge[i].c - d[x]);
//        printf("[%d, %d]:%d, [%d, %d]:%d\n", v, tmp, f[v][tmp], x, vib, f[x][vib]);
        if(tmp > k || tmp < 0) continue ;
        inc(ret, dfs(v, tmp));
        if(flag) return 0;
    }
    vd[x][vib] = 0;
    if(x == n && vib == 0) ++ ret;
    return f[x][vib] = ret;
}

inline void init() { CLR(head, -1), CLR(revh, -1), cnt = cntr = 0, CLR(f, -1), flag = 0; }
int main() {
//    freopen("park.in", "r", stdin);
//    freopen("park.out", "w", stdout);
    int t = rd();
    while(t --) {
        init(); // without short-path initialization
        n = rd(), m = rd(), k = rd(), MOD = rd();
        REP(i, 1, m) {
            int u = rd(), v = rd(), c = rd();
            add(u, v, c), addr(v, u, c);
        }
        spfa(n);
//        QAQ;
//        printf("%d\n", d[1]);
        int ans = 0;
        REP(i, 0, k) { 
            CLR(vd, 0);
            inc(ans, dfs(1, i));
        }
        if(flag) puts("-1"); 
        else printf("%d\n", ans);
    }
    return 0;
}