题解 P1685 【游览】

wuzhaoxin · 2018-12-12 14:31:05 · 题解

拓扑排序+递推

首先看一遍题面，发现一句话：

输入保证这个图没有环，而且从西头到东头至少存在一条路线

我们可以想到这题可能是拓扑排序

假设 cnt[i] 为从 i 到 t 的路径条数 dp[i] 为从 i 到 t 的所有路径的耗时和，那么转移很简单:

（ val[i] 为边的权值）

于是我们可以直接反向建边然后拓扑排序递推出结果，答案为：

#include<bits/stdc++.h>
using namespace std;
inline int gi() {
    register int x,op=1,c;
    while(c=getchar(),c<'0'||c>'9')if(c=='-')op=-op;
    x=c^48;
    while(c=getchar(),c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48);
    return x*op;
}
int head[100001]={0},nxt[1000001],ver[1000001],val[1000001],tot=0;
int dg[100001]={0};
void add(int x,int y,int z) {
    ver[++tot]=y,nxt[tot]=head[x],val[tot]=z,head[x]=tot;dg[y]++;
}
int n,m,s,t;
int dp[100001]={0},cnt[100001]={0};
queue<int>q;
#define mod 10000
void topo() {
    q.push(t);
    cnt[t]=1;
    int x;
    while(!q.empty()) {
        x=q.front(),q.pop();
        for(int i=head[x];i;i=nxt[i])
            cnt[ver[i]]+=cnt[x],cnt[ver[i]]%=mod,dp[ver[i]]+=dp[x]+cnt[x]*val[i],dp[ver[i]]%=mod;
        for(int i=head[x];i;i=nxt[i])
            if(!(--dg[ver[i]]))q.push(ver[i]);
    }
}
int main() {
    n=gi(),m=gi();
    s=gi(),t=gi();
    int t0=gi();
    for(int i=1,x,y;i<=m;i++)
        x=gi(),y=gi(),add(y,x,gi());
    topo();
    printf("%d\n",(dp[s]+(cnt[s]-1)*t0%mod)%mod);
    return 0;
}