题目描述
顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！
你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。
我们把桃花岛抽象成了一个图，共(n)个点代表路的相交处，(m)条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。
你的任务是：把所有不同的路线游览完一共要花多少时间？
输入输出格式
输入格式：
第(1)行为(5)个整数：(n、m、s、t、t0)，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从1到n）和你乘船从岛东头到西头一次的时间。
以下(m)行，每行3个整数：(x、y、t)，表示从点x到点y有一条行走耗时为t的路。
每一行的多个数据之间用一个空格隔开，且：(2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000)
输出格式：
假设总耗时为(total),则输出(total) (mod) (10000)的值（(total)对(10000)取余）。
输入输出样例
输入样例#1：
3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15
输出样例#1：
56
说明
样例解释
共有(3)条路径可以从点(1)到点(3)，分别是(1-2-3,1-2-3,1-3)。
时间计算为：((5+7)+7 +(5+10)+7 +(15)=56)
题解
我们定义
(cnt[i])表示到点(i)的次数；
(dis[i])表示到点(i)的总路径长度。
所以(ans=dis[t]+(cnt[t]-1)*t0)
如何去转移(cnt)和(dis)数组呢
(dfs)一遍不就行了
考虑一条边从(u)到(v)，边权为(w)
(dis[v]=dis[v]+dis[u]+cnt[u]*w;)
(cnt[v]+=cnt[u];)
初始化:(cnt[s]=1)
但是绝对不能直接(dfs)去遍历，只能得(20)分。
我一开始就直(dfs)，还是太菜了（20分）。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
#define mod 10000
#define N 50005
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
int n,m,s,t,ti,tot,h[N];
ll cnt[N],dis[N];
struct node{
int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
edge[++tot].nex=h[u];
edge[tot].to=v;
edge[tot].dis=w;
h[u]=tot;
}
inline void dfs(R int x){
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
(dis[xx]+=dis[x]+cnt[x]*edge[i].dis)%=mod;
(cnt[xx]+=cnt[x])%=mod;
dfs(xx);
}
}
int main(){
read(n);read(m);read(s);read(t);read(ti);
for(R int i=1,u,v,w;i<=m;i++){
read(u);read(v);read(w);
if(u!=v)add(u,v,w);
}
cnt[s]=1;
dfs(s);
printf("%lld
",(dis[t]+(cnt[t]-1)*ti)%mod);
return 0;
}
为什么这样不对？？
因为有一些点的信息我们还没有收集全面就用它去更新其他点了。
如何解决（感谢(wtx)大佬指导），
拓扑排序呀，当一个点入度为0时就说明已经没有点可以去更新它了，说明它的信息收集已经完全了。
正确的代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
#define mod 10000
#define N 50005
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
int n,m,s,t,ti,tot,h[N],in[N];
ll cnt[N],dis[N];
struct node{
int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
edge[++tot].nex=h[u];
edge[tot].to=v;
edge[tot].dis=w;
h[u]=tot;
in[v]++;
}
inline void dfs(R int x){
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
(dis[xx]+=dis[x]+cnt[x]*edge[i].dis)%=mod;
(cnt[xx]+=cnt[x])%=mod;
--in[xx];//拓扑排序
if(!in[xx])dfs(xx);
}
}
int main(){
read(n);read(m);read(s);read(t);read(ti);
for(R int i=1,u,v,w;i<=m;i++){
read(u);read(v);read(w);
if(u!=v)add(u,v,w);
}
cnt[s]=1;
dfs(s);
printf("%lld
",(dis[t]+(cnt[t]-1)*ti)%mod);
return 0;
}