NOIP2017 Day1 T3(最短路+记忆化搜索/最短路+拓扑排序+DP)

发表于 | 分类于 | | + s

Loj 2316
题意：$n$个点，$m$条边的有向图，$1$到$n$最短路为$d$, 求路径长度不超过$d+k$且长度大于等于$d$的路径条数，答案模$p$。
本题 30 分做法直接 Dij 转移时顺带记录最短路条数。$dp(u)$为到$u$最短路$1,u$路径条数, $dp(u)=(\sum dp(v)|dis(1, v)+w=dis(1, u)), dp(u)=(dp(v)|dis(1, v)+w≠dis(1, u))$

考虑 70 分无 0 边，那么我们可以用 30 分做法的 DP 思想来做。这里 $k$ 很小，所以 DP 状态中肯定有一维这个。所以在原基础上加维即可。设$dp(u,j)$为到$u$点$u , n$实际路径长比$u , n$最短路多$j$的路径条数。对于边$(u,v,w)$转移$dp(u,j)=\sum dp(v, j + dis_u - w - dis_{v})。 dis_i$是$(i,n)$最短路，可以记忆化搜索来做。或者如果枚举的顺序就要先更新$dis$ 大的状态，排序以后 DP 即可

然后就是有 0 边了，如果存在一个 0 环，那么这个路径条数将是无限大的，并且记忆化搜索会出现后效性。在记忆化搜索中，如果有一个状态还没有得出值但是被又访问了，那么图中存在 0 环。
也可以将 0 边弄出来单独一个图做拓扑排序，用 0 边的拓扑序来更新，如果拓扑图中出现 0 环，那么原图中也有 0 环。

注意初值的问题，如果让$dp(n,0)=1$，最后答案是$\sum_{i=0}^k dp(1, i)$。如果让$dp(n,i)=1,0\leq i \leq k$, 那么最后答案是$dp(1, k)$。

知识点：
1、最短路计数思想是 DP 思想
2、任何最优化问题/计数问题都可能 DP，只要调换顺序能保证无后效性就能做
3、DP 不想考虑顺序可以用记忆化搜索
4、图中转移和拓扑序有关
5、学一种做法要理解透彻他的思想，Floyd 是一种 DP 思想，本题也是一种 DP 思想
6、数据小的要合理利用这个数据

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 100000 + 5, MAXM = 200000 + 5, INF = 1000000000;

struct edge {int v, w, nxt;} ed[MAXM * 2], ED2[MAXM * 2];
struct data {int u, dis; bool operator < (const data &b) const {return dis > b.dis;} };

int n, m, k, p, en, EN2, flag, hd[MAXN], HD2[MAXN], vis[MAXN], dis[MAXN], dp[MAXN][55], ex[MAXN][55];
std::priority_queue<data > q;

void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void INS2(int u, int v, int w) {ED2[++EN2] = (edge){v, w, HD2[u]}, HD2[u] = EN2;}

void dij() {
    for (int i = 0; i <= n; i++) dis[i] = INF;
    q.push((data){n, 0}), dis[n] = 0;
    while (!q.empty()) {
        data b = q.top(); q.pop();
        if (vis[b.u]) continue; vis[b.u] = true;
        for (int i = HD2[b.u]; i > 0; i = ED2[i].nxt) {
            edge &e = ED2[i];
            if (dis[e.v] > dis[b.u] + e.w) dis[e.v] = dis[b.u] + e.w, q.push((data){e.v, dis[e.v]});
        }
    }
}
int f(int u, int j) {
    if (ex[u][j]) return flag = 1, -1;
    if (dp[u][j]) return dp[u][j];
    ex[u][j] = 1;
    for (int i = hd[u]; i > 0; i = ed[i].nxt) {
        edge &e = ed[i];
        int tmp = j + dis[u] - e.w - dis[e.v];
        if (tmp >= 0) dp[u][j] = (dp[u][j] + f(e.v, tmp)) % p;
    }
    return ex[u][j] = 0, dp[u][j];
}

void clean() {
    flag = en = EN2 = 0, ms(hd, 0), ms(HD2, 0), ms(vis, 0), ms(dp, 0), ms(ex, 0);
}
int solve() {
    clean();
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for (int a, b, c, i = 1; i <= m; i++) scanf("%d%d%d", &a, &b, &c), ins(a, b, c), INS2(b, a, c);
    dij(); 
    //for (int i = 1; i <= n; i++) printf("%d%c", dis[i], (i == n ? '\n' : ' '));
    int ans = 0;
    dp[n][0] = 1;
    for (int i = 0; i <= k; i++) ans = (ans + f(1, i)) % p;
    //for (int i = 0; i <= k; i++) printf("%d%c", dp[1][i], (i == k ? '\n' : ' '));
    if (flag) printf("-1\n"); else printf("%d\n", ans);
    return 0; 
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}
------ 本文结束 ------