2 条题解

  • 2
    @ 2023-10-19 23:48:57

    考虑一种最简单的状态

    fv,jf_{v,j} 为走到点 vv 路线长度恰为 jj 的方案数。转移则是枚举从哪个点走过来。

    fv,j=fu,jwf_{v,j}=\sum f_{u,j-w}u>vu->v 边权为 ww

    这么做的状态是非常多的,但是我们可以发现有一个 kk 的限制,导致很多第二维状态没有用处。例如设 1n1\sim n 的最短路为 dd

    对于 j<dj<d 的状态 jj 必然为 00,实际需要求的也仅仅是 fn,d+fn,d+1++fn,d+kf_{n,d}+f_{n,d+1}+\dots+f_{n,d+k} 只有 k+1k+1 个状态是合法的

    对于其余的某个点 vv 设到达点 vv 的最短路是 dvd_vjj 必须 jdvj\geq d_v

    同时必须满足 jdv+kj\leq d_v+k

    简单证明来说,若走到 vv 第二维 jj 已经大于 dv+kd_v+k 则后续不管怎么走走到 nn 的路径长度必然大于 d+kd+k

    故而对于任意点 vv 只需要考虑 k+1k+1 个状态。

    重新修改状态,设 fv,jf_{v,j} 为从起点走到 vv 且路径长度恰好为 dv+jd_v+j 的所有路线数量,相当于第二维是最短距离加偏移量。

    状态转移:由于第二维寸的是一个偏移量,考虑某个点 uu 走到 vv ,点 vv 此时第二维状态 jj ,实际走到 vv 的真实距离是 dv+jd_v+j 则走到 uu 的真是距离应为 dv+jwd_v+j-w,它同时等于 du+xd_u+xxx 为此时走到 uu 的便宜量,则 x=dv+jwdux=d_v+j-w-d_u。即 fv,j=fu,x,x=dv+jwduf_{v,j}=\sum f_{u,x},x=d_v+j-w-d_u

    若有环怎么办?

    首先对于本题来说,如果存在一条路径走到 nn 有环,环上边权和为 00 那么肯定有无限种方案,因此在使用记忆化搜索的同时若出现循环依赖,直接返回负 11 即可。

    具体步骤

    • 使用最短路算法预处理最短路 did_i
    • 记忆化搜索搜索 fn,0,fn,1,,fn,kf_{n,0},f_{n,1},\dots,f_{n,k}
    • 记忆化搜索可以存反图,从终点开始搜索,这是为了保证求解的正确性,因为图中的某些点不一定能到达 nn 假如走到一个环,且该环无法到达 nn 则导致了后续求解的错误。
    • 对于判断是否存在 00 的环路,则看一个状态是否重复访问即可,设置一个判重数组来判断状态是否重复访问。
    #include <bits/stdc++.h>
    #define ll long long
    #define p pair<int, int>
    #define x first
    #define y second
    using namespace std;
    const int N = 1e5 + 5;
    int n, m, k, mod, d[N], f[N][55];
    vector<p> e[N], ne[N];
    bool vis[N], flag;
    bool instk[N][55];
    void dijkstra()
    {
        memset(d, 0x3f, sizeof(d));
        memset(vis, 0, sizeof(vis));
        priority_queue<p, vector<p>, greater<p>> q;
        q.push({0, 1});
        d[1] = 0;
        while (q.size())
        {
            auto now = q.top();
            q.pop();
            int u = now.y;
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto road : e[u])
            {
                int v = road.x, w = road.y;
                if (d[v] > d[u] + w)
                {
                    d[v] = d[u] + w;
                    q.push({d[v], v});
                }
            }
        }
    }
    int dp(int u, int j) // f[b][j] 
    {
        if (instk[u][j])
        {
            flag = 1;
            return 0;
        }
        if (f[u][j] != -1) return f[u][j];
        f[u][j] = 0;
        if (u == 1 && j == 0) f[u][j]++;
        instk[u][j] = 1;
        for (auto road : ne[u])
        {
            int v = road.x, w = road.y;
            int x = d[u] + j - w - d[v];
            if (x < 0 || x > k) continue;
            f[u][j] = (f[u][j] + dp(v, x)) % mod;
            if (flag) return 0;
        }
        instk[u][j] = 0;
        return f[u][j];
    }
    void solve()
    {
        cin >> n >> m >> k >> mod;
        for (int i = 1; i <= n; i++) e[i].clear(), ne[i].clear();
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e[u].push_back({v, w}), ne[v].push_back({u, w});
        }
        dijkstra();
        memset(f, -1, sizeof(f));
        int res = 0;
        flag = 0;
        memset(instk, 0, sizeof(instk));
        for (int i = 0; i <= k; i++)
        {
            res = (res + dp(n, i)) % mod;
            if (flag) 
            {
                res = -1;
                break;
            }
        }
        cout << res << "\n";
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t--) solve();
        return 0;
    }
    
    • @ 2024-1-7 18:32:35

      老师厉害呀,我给你点了赞👍

  • 0
    @ 2024-1-7 18:33:22

    这道题太难了,不会做

    • 1

    信息

    ID
    1387
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    25
    已通过
    13
    上传者