P1685 题解

· · 题解

题目分析

这是一道借助拓扑排序实现递推的题。

首先我们考虑递推式子：我们定义 ct_x 表示经过 x 这个点几次，tme_x 表示以 x 这个点为终点的最多游览时间（不考虑从西头回到东头的），w(x, y) 表示 x 到 y 这条边所耗时间。对于 x 的出边所到达的点 y ，我们可以考虑一下 x 对 y 的贡献是什么：很显然，tme_y 要加上 tme_x 和 ct_x \times w(x, y)，从 x 转移到 y 不仅以往的要转移过来，还有走路径的贡献：经过 x 这个点几次就要走几次 (x, y) 这条路，用 ct_x 乘上边权就可以把所有贡献全计算上，这样 x 这个点就不用考虑了。所以第一个递推式子是：tme_y += tme_x + ct_x \times w(x, y) 我们还要考虑 ct 的转移：既然可以经过 x 节点 ct_x 次，那对于 y 肯定也能经过 ct_x 次，所以还要：ct_y += ct_x。

递推的过程可以通过拓扑排序来实现，因为拓扑排序总是将入度为 0 的点加入，而将拓展完的节点舍去，而对于本题这个性质刚好：对于一个点，只有他的贡献被算清楚不会再变动时，我们才能安心地用它来递推，这时就是处理完他的所有入边的时候。

最后我们只要输出 tme_t + (ct_t - 1) \times t_0 模 10000 的值就行了。

代码

注意一下关键字 time 哦（还有缩写成 tm 没想到也是关键字结果就 CE 了挺郁闷）

#include <bits/stdc++.h>
#define int long long
#define maxn 10005
#define inf 1e9
#define mod 10000
using namespace std;
inline int read() { //来自 xjz 巨佬的快读
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int n, m, s, t, t0;
int ct[maxn], tme[maxn];
int in[maxn];
struct edge {
    int v, w, nxt;
}e[maxn];
int head[maxn], cnt;
void add(int u, int v, int w) {
    e[++cnt].v = v, e[cnt].w = w;
    e[cnt].nxt = head[u], head[u] = cnt;
}

signed main() {
    n = read(), m = read(), s = read(), t = read(), t0 = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        in[v]++;
    }

    //拓扑排序
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i), ct[i] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].v, z = e[i].w;
                //递推式子，上面有解释，注意实时模 mod ,一个也不能少
            tme[y] = (tme[y] + tme[x] + ct[x] * z) % mod;
            ct[y] = (ct[y] + ct[x]) % mod;
            if (--in[y] == 0) q.push(y);
        }
    }
    cout << (tme[t] + (ct[t] - 1) * t0 % mod) % mod;
}

完结撒花——