题解 P1685 【游览】

· · 题解

题目大意就是求两个值tot_1,tot_2的和

$tot_2:$为每次从终点$T$回到起点$S$的耗时和 因为终点回到起点的时间是固定的，所以我们只要知道有几条从起点到终点的路径 不妨设： $\large f_x:$ 起点到点$x$的路径数 $\large G_x:$ 终点到点$x$的路径数 不过这要怎么求呢？ 根据题意得，这是个拓扑图，也就是说不存在环，点之间存在相对顺序 然后就用拓扑正反刷两趟即可 得出$f_x$和$G_x$后，我们就求出了$tot_2$，即 $$\Large tot_2=t_0\times f_T(G_1)$$ 再考虑$tot_1

对于一条边x\rightarrow y，我们需要求出有多少路径经过

根据乘法原理，经过次数\large Cnt=f_x\times G_y

所以这条边对答案的贡献即为（w为边权）：

\Large f_x\times G_y\times w

对每条边都这么统计一次答案就出来了

code:

#include<bits/stdc++.h>
#define maxn 200005
#define maxe 1000005
using namespace std;
const int TT=10000;
int n,Ans,m,lnk[maxn],S,T,t,nxt[maxe],son[maxe],w[maxe],tot,T_in[maxn],G[maxn][2],x[maxe],y[maxe],z[maxe],Q[maxn],hed,til;
bool vis[maxn];
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
inline void add(int x,int y,int z){if (x==y) return;nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;w[tot]=z;}
int main(){
    n=read(),m=read(),S=read(),T=read(),t=read();
    for (int i=1;i<=m;i++) T_in[x[i]=read()]++,y[i]=read(),z[i]=read(),add(y[i],x[i],z[i]);
    for (int i=1;i<=n;i++) if (!T_in[i]) Q[++til]=i,vis[i]=G[i][0]=1;
    while (hed<til){
        hed++;int Now=Q[hed];
        for (int i=lnk[Now];i;i=nxt[i]){
            if (vis[son[i]]) continue;
            if (!--T_in[son[i]]) Q[++til]=son[i],vis[son[i]]=1;
            G[son[i]][0]=(G[son[i]][0]+G[Now][0])%TT;
        }
    }
    memset(vis,0,sizeof vis);
    memset(lnk,0,sizeof lnk);
    memset(T_in,0,sizeof T_in);
    hed=tot=til=0;
    for (int i=1;i<=m;i++) T_in[y[i]]++,add(x[i],y[i],z[i]);
    for (int i=1;i<=n;i++) if (!T_in[i]) Q[++til]=i,vis[i]=G[i][1]=1;
    while (hed<til){
        hed++;int Now=Q[hed];
        for (int i=lnk[Now];i;i=nxt[i]){
            if (vis[son[i]]) continue;
            if (!--T_in[son[i]]) Q[++til]=son[i],vis[son[i]]=1;
            G[son[i]][1]=(G[son[i]][1]+G[Now][1])%TT;
            Ans=(Ans+G[Now][1]*G[son[i]][0]%TT*w[i]%TT)%TT;
        }
    }
    printf("%d",(Ans+(G[S][0]-1)*t%TT)%TT);
    return 0;
}