题解 P1685 【游览】

· · 题解

P1685 【游览】

题目传送门

因为本人太蒻了，调了30分钟，还是挂了，于是在学习完题解后，重写这道题。

因为该题给出的图是DAG（有向无环图），其实这题本质上就是一道拓扑排序了。

我们记一个cnt数组来存储到点i的次数，in数组来存储各个点的入度，dis数组来存储到点i的总长度，e数组链式前向星存边。

推一下式子可得：

dis[v]=dis[v]+dis[u]+cnt[u]×e[i].w cnt[v]+=cnt[u] ans=dis[t]+(cnt[t]-1)×t_0

ACcode如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e4;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
struct node{
    int u,v,w;
}e[maxn];
int n,m,s,t,t0,pos,in[maxn],head[maxn],dis[maxn],cnt[maxn];
inline void add(int u,int v,int w){
    e[++pos].u=head[u],e[pos].v=v,e[pos].w=w,head[u]=pos;
    //链式前向星存边 
}
inline void dfs(int u){
    for(int i=head[u];i;i=e[i].u){
        int v=e[i].v;
        dis[v]=(dis[v]+dis[u]+cnt[u]*e[i].w)%mod,cnt[v]=(cnt[v]+cnt[u])%mod,in[v]--;
        if(!in[v])dfs(v);
        //如果当前入度不为0，则继续更新 
    }
}
inline int read();
int main(int argc, char const *argv[]){
//  std::ios::sync_with_stdio(false);
    n=read(),m=read(),s=read(),t=read(),t0=read(),cnt[s]=1;
    for(int i=1,u,v,w;i<=m;++i){
        u=read(),v=read(),w=read(),in[v]++;
        add(u,v,w); 
    }
    dfs(s);
    cnt[t]--;
    //最后一次游览时不需要回去了 
    printf("%d",(dis[t]+cnt[t]*t0)%mod);
    return 0;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}

本篇题解就到此结束了，如果喜欢，还请点个赞吧。