题解 P1685 【游览】

· · 题解

我真是菜鸡，题读了半天才懂，代码敲出来调了1个多小时，结果是输入打错了。

My vegetable has exploded……

咳咳

思路

这题我真的读了很久，一直没搞懂是啥意思……

我先来解释一下题意，

就是有一个DAG，有一个起点s和一个终点t。

这个人要从起点s走完所有可以到达终点t的方案，求出他所走过的每一条方案的边权和tot_1；而且，每当他走完一个方案来到终点t时，如果还有方案没走过，他就要花t0的时间重新回到起点s，要求出他从终点t回到起点s的时间和tot_2。答案ans=tot_1+tot_2。

理解了题意，可以想想怎么做了。

首先，他给出的图是一个DAG。

其次他还让我们求所有方案的和。

假设count_i为到i的次数。dis_i表示到点i的总路径长度。

很明显，我们可以用拓扑排序+递推的思想，根据起点count_1=1，推出count_2,count_3...count_n。

假设，点i的下一个点为j，那么count_j一定包含了count_i，画个图就知道了。

所以，如果当前点为i，那么count_i为所有到它的点的count之和。

相类似的，当前点i的dis_i即为到它的点的dis值和（count_i \times 到i的所有边的权值）的总和。

好了，有点绕，看代码

code

#include<cstdio>
#include<queue>
using namespace std;

const int mod=10000;
const int maxn1=1e4+7;
const int maxn2=5e4+7;

struct edge{int to,next,w;}map[maxn2];

int n,m,s,t,t0,in[maxn1],count[maxn1],dis[maxn1];
int cnt,head[maxn1];
queue<int>q;

int read(){
    char ch=getchar();int f=1,r=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}
    return f*r;
}

void add(int x,int y,int w){
    map[++cnt].to=y;
    map[cnt].w=w;
    map[cnt].next=head[x];
    head[x]=cnt;
    in[y]++;
    return ;
}

void toposort(){
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=map[i].next){
            int y=map[i].to,w=map[i].w;
            (dis[y]+=dis[x]+count[x]*w)%=mod;
            (count[y]+=count[x])%=mod;
            if(!(--in[y])) q.push(y);
        }
    }
    return ;
}

int main(){
    n=read(),m=read(),s=read(),t=read(),t0=read();
    //for(int i=1;i<=m;i++) add(read(),read(),read());//调了一个小时
    int x,y,w;
    for(int i=1;i<=m;++i) x=read(),y=read(),w=read(),add(x,y,w);
    count[s]=1;
    toposort();
    printf("%d",(dis[t]+(count[t]-1)*t0)%mod);//当他最后一次游览时，就不需要回去了，所以-1。
    return 0;
}