P1685 游览 - 洛谷
P4017 最大食物链计数 - 洛谷
已知一个 DAG 和起点 \(s\) 终点 \(e\) 和从终点回起点的时间 \(t\) ，如果从起点到终点如果有多条可选择的路径，那么要全部走一遍。问总耗时多少（对 \(10000\) 取模）。
假如从 \(e\) 回到 \(s\) 的次数为 \(cnt_e\) ，不难看出返回起点的总时间为 \((cnt_e-1)\times t\) 。
初始化 \(cnt_s=1\) 其余为 \(0\) 按转移方程 cnt[v] += cnt[u] 递推
初始化 \(dp\) 数组定义为从起点到当前节点的总距离，转移方程为 dp[v] += dp[u] + cnt[u] * w 。
看图片更好理解第二个转移方程
转移方程执行流程图
具体代码为
import sys
from collections import deque
from math import inf
if 1:inp = lambda: sys.stdin.readline().strip()II = lambda: int(inp())MII = lambda: map(int, inp().split())LII = lambda: list(MII())Max = lambda x, y: x if x > y else yMin = lambda x, y: x if x < y else ydef main():n, m, s, e, t = MII()g = [[] for _ in range(n + 1)]din = [0] * (n + 1)for _ in range(m):u, v, w = MII()g[u].append((v, w))din[v] += 1dq = deque([i for i in range(1, n + 1) if din[i] == 0])cnt = [0] * (n + 1)cnt[s] = 1dp = [0] * (n + 1)while dq:u = dq.popleft()for v, w in g[u]:cnt[v] += cnt[u]dp[v] += dp[u] + cnt[u] * wdin[v] -= 1if din[v] == 0:dq.append(v) ans = (cnt[e] - 1) * t + dp[e]print(ans % 10000)if __name__ == "__main__":main()
第二道题要比上一道简单，这里只需要统计经过多少次即可，初始化所有源点为 \(1\) 转移方程为前面的第一个转移方程 dp[v] += dp[u]
唯一要注意的点是结果是所有汇点的和。
食物链条数图
具体代码为
# 模版代码直接复制即可
def main():n, m = MII()g = [[] for _ in range(n + 1)]din = [0] * (n + 1)dout = [0] * (n + 1)for _ in range(m):u, v = MII()g[u].append(v)din[v] += 1dout[u] += 1dq = deque([i for i in range(1, n + 1) if din[i] == 0])dp = [0] * (n + 1)for i in dq:dp[i] = 1while dq:u = dq.popleft()for v in g[u]:dp[v] += dp[u]dp[v] %= MODdin[v] -= 1if din[v] == 0:dq.append(v)print(sum(dp[i] for i in range(1, n + 1) if dout[i] == 0) % MOD)if __name__ == "__main__":main()