题解 P1695

Democlight · 2022-09-17 16:22:39 · 题解

令cnt[i]表示从t到i的路径数 All[i]表示从t到i的总路径长

不难想到dp 对于每个节点i，有：

cnt[i]=Σcnt[pre[i]]

All[i]=ΣAll[pre[i]]+cnt[pre[i]]*w[pre[i]][i]

问题出在处理节点的先后顺序 每个节点i处理之前，当且仅当所有pre[i]都被处理过

于是不难想到topo排序

代码：：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
    for(;isdigit(ch);ch=getchar())ret=(ret<<1)+(ret<<3)+(ch&15);
    return ret*f;
}
#define TT 10000
#define maxn 10005
#define maxe 100005
int tot,lnk[maxn],nxt[maxe],w[maxe],son[maxe],per;
void add(int x,int y,int z){w[++tot]=z,nxt[tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
struct AC{
    int y,w;
};
vector<AC>e[maxn];bool vis[maxn];int que[maxn];
void BFS(int t){
    int len=e[t].size();
    vis[t]=1;for(int i=0;i<len;i++)if(!vis[e[t][i].y])BFS(e[t][i].y);
}
int du[maxn],cnt[maxn],All[maxn];
long long Topo(int t,int s){
    que[1]=t;cnt[t]++;
    int head=0,tail=1;
    while(head^tail){
        for(int j=lnk[que[++head]];j;j=nxt[j]){
            if(!--du[son[j]])que[++tail]=son[j];
            cnt[son[j]]=(cnt[son[j]]+cnt[que[head]])%TT;
            All[son[j]]=(All[son[j]]+cnt[que[head]]*w[j]+All[que[head]])%TT;
        }
    }
    return (All[s]+(cnt[s]-1)*per)%TT;
}
int main(){
    freopen("1.in","r",stdin);
    int n=read(),m=read(),t=read(),s=read();per=read();
    for(int i=1;i<=m;i++){
    int x=read(),y=read(),z=read(); e[x].push_back((AC){y,z});
    }
    BFS(t);
    for(int i=1;i<=n;i++){
        if(!vis[i])continue;
        int len=e[i].size();
        for(int j=0;j<len;j++)du[e[i][j].y]++,add(i,e[i][j].y,e[i][j].w);
    }
    printf("%lld",Topo(t,s));
}