P1685 游览

· · 题解

题解

思路

看到有权有向图，想到拓扑排序。题目中询问的是最后的总时间，计算方法为：\sum _{i=1}^{num} t_i+t_0*(num-1)，其中 num 为从岛西头到达岛东头的路径数量，t_i 为每一条从岛西头到达岛东头路径上的总时间，因为最后一次不需要返回，所以只用乘 num-1 次船。有了思想后，实现的过程就是用拓扑排序去更新这两个值。

细节

  1. 更新时间不仅要加上前驱的时间 tim[x]，还要加上走这一条边的用时 t 乘上到达前驱的路径总数量 cnt[x]。注意不是只加一个 t，请读者自己想原因。
  2. 建议使用链式前向星存图。

AC code


#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5,mod=1e4;
int n,m,s,l,t,head[N],tot,p[N],cnt[N],tim[N];
struct node
{
    int next,to,dis;
}edge[5*N];
void add(int from,int to,int dis)
{
    tot++;
    edge[tot].to=to,edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
queue<int>q;
signed main()
{
    cin>>n>>m>>s>>l>>t;
    while(m--)
    {
        int x,y,d;
        cin>>x>>y>>d;
        add(x,y,d);
        p[y]++;
    }
    for(int i=1;i<=n;i++)
        if(p[i]==0)
        {
            q.push(i);
            cnt[i]=1;
        }
    while(q.size())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            p[y]--;
            tim[y]=(tim[y]+tim[x]+edge[i].dis*cnt[x])%mod;
            cnt[y]=(cnt[y]+cnt[x])%mod;
            if(p[y]==0)q.push(y);
        }
    }
    cout<<(tim[l]+(t*(cnt[l]-1))%mod)%mod;
    return 0;
}