本文最后更新于：2023年4月26日 晚上
题目大意
给你一个 DAG
（有向无环图），给你起点和终点，求所有从起点到终点的路径的时间之和，以及方案数减一乘上渡船时间，数据保证能从起点到达终点。
分析
首先考虑暴力 dfs
，但通过分析，可以发现这是一种不可行的策略，因为搜索到某个点时，到它的所有路径不一定被搜完，如果直接搜下去会影响正确性，如果回溯重新搜索会浪费时间。
于是我们就要在搜索到一个点时使得它的入度为零，可以利用拓扑排序实现，同时利用一个类似动态规划加
bfs 的思路记录目前到达这个点的方案数和目前所有路径长度之和。
这道题的转移方程：
\[
dp[to][0]=\sum dp[from][0]
\\
dp[to][1]=\sum dp[from][0] \times length + dp[from][1]
\]
其中 \(to\) 表示东边的点， \(from\) 表示西边的点 ， \(dp[i][0]\) 表示到第 \(i\) 个点的路径数量， \(dp[i][1]\) 表示目前到第 \(i\) 个点的路径长度总和。
同时，这道题的边最好使用类似链式前向星的思路实现，使用 vector
会使代码难度及时间复杂度变高。
代码（比较长，看不懂请留言）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| struct edge {
int from,to,length;
int lst,nxt;
};
edge led[50005]={};
int dis[20005][2]={},ed[20005][2]={},cnt[20005]={};
void wk() {
memset(ed,-1,sizeof ed);
int n,m,st,edt,tm;
read(n),read(m),read(st),read(edt),read(tm);
dis[st][0]=1;
for(int i=1;i<=m;++i) {
int fr,to,val;
read(fr),read(to),read(val);
led[i].from=fr;
led[i].to=to;
led[i].length=val;
led[i].lst=ed[fr][1];
led[i].nxt=-1;
cnt[to]++;
if(ed[fr][0]==-1) ed[fr][0]=ed[fr][1]=i;
else {
led[ed[fr][1]].nxt=i;
ed[fr][1]=i;
}
}
deque<int> que;
for(int i=1;i<=n;++i) {
if(!cnt[i]) {
que.push_back(i);
}
}
while(!que.empty()) {
int node=que.front();
que.pop_front();
for(int i=ed[node][0];i!=-1;i=led[i].nxt) {
(dis[led[i].to][0]+=dis[node][0])%=10000;
(dis[led[i].to][1]+=dis[node][0]*led[i].length+dis[node][1])%=10000;
if(!(--cnt[led[i].to])) {
que.push_back(led[i].to);
}
}
}
write((1ll*dis[edt][1]+1ll*(dis[edt][0]-1)*tm)%10000);
}
|