P1685 题解

· · 题解

前言

首先我们了解一下题意：给你一个 n个点，m 条边的有向图，再你给一个起点 s，终点 t，以及它们之间的距离，问你这个图中从起点 s 到终点 t 的所有路径之和，并对 10^4 取模。

注意：每一个路径到达终点后，需要通过它到起点的距离再次回到起点进行下一次遍历。

具体思路

  1. 首先考虑暴力：对于此题，暴力的做法就是挨个去试每一条路径，并记录下来这条路径上所有点的和，如果这条路径可以到达终点，就用计数变量加上这条路径上的和。但是我们观察到 n \leq 10^4 且 m \leq 5 \times 10^4，这个做法的时间复杂度显然通过不了。

  2. 再考虑正解：想一个问题：暴力为什么会超时？因为我们是每一路径都去遍历了一遍，但是有些路径会被重复遍历，这就是导致我们超时的原因。那么怎么解决呢？当然是预处理。我们预处理出每一个点会被几个路径包含，那么从起点到这个点的每条路径之和显然也可以一起算出来，只需要将可以到达这个点的所有点的路径之和的总和加上这些点到当前点的路径就可以啦。建议带着样例模拟一下。

  3. 那我们怎么保证现有的点的状态就是确定的呢？考虑一个事实：当这个点再也不会被更新之后它就已经确定了，而更新的条件则是有点能到达它，这个条件显然可以用拓扑图维护。所以我们确定了我们的算法：拓扑图上跑 dp。

  4. 最后在考虑每次路径走完后都要回到起点的和，这个非常好算，只需要求出总路径的个数，再用总路径的个数减一乘从终点回到起点的路程就完了。输出时注意取模。

AC code

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N=1e4+10,mod=10000;
int n,m;
int d[N];//记录每个点的入度 
int s,t,p;
int cnt[N];//记录每个点可以被多少个点到达 
int ans[N];//记录从起点到这个点的所有路径的和 
int h[N],idx=0;
struct Node{
    int w;
    int to,ne;
}tr[N];
void add(int u,int v,int w){
    tr[idx].w=w,tr[idx].to=v,tr[idx].ne=h[u],h[u]=idx++;//建单向图 
}
void top(){
    queue<int> q;
    q.push(s);//将起点放入队列 
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];i!=-1;i=tr[i].ne){
            int to=tr[i].to;
            cnt[to]+=cnt[u],ans[to]=(ans[to]+ans[u]+cnt[u]*tr[i].w)%mod;
            //这个点可以被到达u的所有点到达，它的路径和要加等于u的路径和并加上这些点到当前点的总和 
            if(!(--d[to])) q.push(to);//如果这个点的入读为0，说明它不会再被更新了，于是放入队列。 
        }
    }
} 
signed main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    cin>>s>>t>>p;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        d[v]++,add(u,v,w);//建图操作 
    }
    cnt[s]=1,top();//将起点的到达数设为1，进行拓扑排序 
    cout<<(ans[t]+(cnt[t]-1)*p)%mod<<endl;//输出从起点到终点的所有路径和加上路径数减一乘起点到终点的路程 
    return 0;//
}