P1685 游览 DP+拓扑排序

· · 题解

题目解析：

本题是一道经典的拓扑排序题目，题目要求我们求出从西头到东头的所有不同的路线游览完的时间总和，而且规定所有的路线不能完全相同。

我们可以将问题转化成从西头到东头，每次不能走之前走过的路径，求出最短路程。

由于题目保证没有环，我们可以使用拓扑排序算法求出从西头到东头的一个拓扑序列。

再根据拓扑序列从西头开始遍历每个节点，不断更新从西头到每个节点的最短路程。

具体来说，我们可以定义一个数组 dist，其中 dist[i] 表示从西头到点 i 的最短路程。在拓扑排序过程中，我们从西头开始访问每个节点 u，遍历 u 的所有出边 (u,v)，如果更新 v 的最短路程 dist[v] 可以使得 dist[v] 更小，则更新 dist[v]。由于题目保证没有环，每个节点只会被遍历一次，因此时间复杂度为 \mathcal{O}(n+m)。

最后，我们的目标是求出从西头到东头的所有不同的路线游览完的时间总和。我们可以使用类似于背包问题的思想，对于每个节点 i，我们维护一个 dp 数组，其中 dp[j] 表示从西头到点 i，经过了 j 条边的所有不同的路线游览完的时间总和。

初始时 dp[0]=0，遍历 i 的所有入边 (u,i)，对于每个 j，如果 j>0，我们可以从 dp[j-1] 转移而来，增加 t_0 的时间消耗。由于题目要求所有的路线不能完全相同，因此当 (u,i) 是第一条入边时，我们无法从 dp[j] 转移而来，只能从 dp[j-1] 转移而来。

更新完 dp 数组后，我们将 dp 数组中的所有元素累加起来，即可得到从西头到东头的所有不同的路线游览完的时间总和。

时间复杂度为 \mathcal{O}(n+m)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100100,mod=10000;
inline ll read(){
    ll 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<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
int n,m,s,t,t0,z[N],top;
int h[N],ans,a[N],dp[N],G[N];
struct Node{
    int u,v,w;
}E[N<<2];
inline void add(int x,int y,int z){
    E[++ans].u=h[x];
    E[ans].v=y;
    E[ans].w=z;
    h[x]=ans;
}
inline void Tsort(){
    for(int i=1;i<=n;i++)
      if(!a[i])
        z[++top]=i,G[i]=1;
    while(top){
        int u=z[top--];
        for(int i=h[u];i;i=E[i].u){
            a[E[i].v]--;
            (dp[E[i].v]+=dp[u]+G[u]*E[i].w)%=mod;
            (G[E[i].v]+=G[u])%=mod;
            if(!a[E[i].v])
              z[++top]=E[i].v;
        }
    }
}
int main(){
    n=read(),m=read(),s=read(),t=read(),t0=read();
    for(int i=1,x,y,z;i<=m;i++){
        x=read(),y=read(),z=read();
        if(x==y)
          continue;
        add(x,y,z);
        a[y]++;
    }
    Tsort();
    write((dp[t]%mod+(G[t]-1)*t0)%mod);
    return 0;
}

大家可以自己推一下，不要抄哦~