题解 P1685 【游览】

ZAGER · 2018-10-19 18:58:20 · 题解

题解

最美的透彻

我们定义

如何去转移cnt和dis数组呢

初始化: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\n",(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\n",(dis[t]+(cnt[t]-1)*ti)%mod);
    return 0;
}