NOIP2017d1t3逛公园题解

策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从N号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到N号点的最短路长为d，那么策策只会喜欢长度不超过d + K的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对P取模。

如果有无穷多条合法的路线，请输出-1。

AFO时长一年后难得又写了一道题.

这个题看起来有些复杂. 我们不妨先考虑弱些的情况

保证公园的地图是一张DAG

这个情形就很显然是个树形dp. 不难设计出状态转移方程

设$dis[u]$是”从$u$到终点的最短路”, $moew(u,hp)$表示”策策处在$u$点, 体力为$dis[u]+hp$时, 恰好耗尽体力走到终点的方案数”, 容易得到转移方程:
$$
meow(u,hp)=\sum_{v} meow(v,dis[u]+hp-edge[u\ to\ v].length-dis[v])
$$
其中$v$是所有$u$可以直接连向的点

由于$0\leq hp\leq k\leq$, 故复杂度为$O(n\times hp)$

地图中存在环, 但保证不存在零环

这个时候上述转移方程还是否适用呢?

笔者在这里陷入了一个误区: 如果存在环的话, 策策就可以多次走到同一个点. 这样一个点就会被多次处理, 看起来不具备无后效性啊

请注意: **我们所设计的状态不是 “策策处在$u$点” , 而是 “体力为$dis[u]+hp$的策策处在$u$点” **

如果不存在零环的话, 策策虽然可以多次走到$u$点, 但是每次走到$u$点时的$hp$是一定不同的. 永远只有一个“处在$u$点的体力为$dis[u]+hp$的策策”.

也就是说$meow(u,hp)$的值一定只会被计算一次, 满足无后效性. 上述方程仍然成立. 时间复杂度依然为$O(n\times hp)$

(AFO久了脑子就不太好使了.)

地图中存在零环

顺着上面的思路, 没有零环时每次走到$u$点时的$hp$是一定不同的. 那么也就是说”有零环时会有两次走到$u$点时$hp$是相同的”. 通过这个性质就可以轻松地判断$u$点上是否在一个零环上.

值得注意的特殊情况:

$meow(终点,0)=1$是dp的边界条件, 那么使用上述的判零环方法会忽略”终点在一个零环上”的情况. 因为这种情况发生时$moew(终点,0)=+\infty$, dp的边界条件被破坏了.

特判”终点在一个零环上”的情况也不难. 只要在做dijkstra的过程中发现有一条指向终点的长度为$0$的最短路, 那么这条最短路就是终点上的零环.

(实话说这个情况要不是样例有我就真的忽略了)

总之代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, m, k, p, T;
//gragh beg
struct edge{
    LL v, cs;
    edge *nxt;
    edge (const LL &be, const LL &ge, edge *de){
        v = be, cs = ge, nxt = de;
        return ;
    }
}*G[200000], *G_[200000];
void del_g(edge **g, LL n){
    for (LL i = 1;i <= n;++ i){
        for (edge *j = g[i], *k;j;k = j, j = j->nxt, delete(k));
        g[i] = NULL;
    }
    return ;
}
//gragh end
//dijkstra beg
LL dis[200000];
bool vis[200000], zero_1;
struct qwq{
    LL v, dis;
    bool operator < (const qwq &al)const{
        return dis > al.dis;
    }
};
void dijkstra(LL s){
    priority_queue<qwq> q;
    q.push((qwq){1, 0});
    while(q.size()){
        qwq al = q.top();
        q.pop();
        if (vis[al.v])
            continue;
        dis[al.v] = al.dis;
        vis[al.v] = 1;
        for (edge *i = G[al.v]; i; i = i->nxt){
            if (vis[i->v]){
                if (i->v == 1 && dis[al.v] + i->cs == 0){
                    //node1 on a zero circle
                    zero_1 = 1;
                    return ;
                }
                continue;
            }
            q.push((qwq){i->v, al.dis + i->cs});
        }
    }
    return ;
}
//dijkstra end
//dp
LL dp[100010][60];
bool sta[100010][60];
LL meow(LL u, LL hp){
    if (sta[u][hp])
    //a zero circle on this road
        return -1;
    if (dp[u][hp] != -1)
        return dp[u][hp];
    sta[u][hp] = 1;
    LL al = 0, hp_;
    for (edge *i = G_[u];i;i = i->nxt){
        hp_ = hp + dis[u] - i->cs - dis[i->v];
        if (hp_ < 0 || hp_ > k)
            continue;
        LL tmp = meow(i->v, hp_);
        if (tmp == -1)
            return -1;
        al = (al + tmp) % p;
    }
    sta[u][hp] = 0;
    return dp[u][hp] = al;
}
//dp end
int main (){
    cin >> T;
    while (T--){
        //initialization
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(dp, -1, sizeof(dp));
        memset(sta, 0, sizeof(sta));
        zero_1 = 0;
        LL al, be, ge;
        scanf("%lld%lld%lld%lld", &n, &m, &k, &p);
        for (LL i = 1;i <= m;++ i){
            scanf("%lld%lld%lld", &al, &be, &ge);
            G[al] = new edge(be, ge, G[al]);
            G_[be] = new edge(al, ge, G_[be]);
        }
        //main
        LL ans = 0;
        dijkstra(1);
        if (zero_1){
            ans = -1;
        }
        else{
            dp[1][0] = 1;
            for (LL i = 0;i <= k;++ i){
                LL tmp = meow(n, i);
                if (tmp == -1){
                    ans = -1;
                    break;
                }
                ans = (ans + tmp) % p;
            }
        }
        printf("%lld\n", ans);
        //initialization
        del_g(G, n);del_g(G_, n);
    }
    return 0;
}

文结.