洛谷 P1685 游览
题目描述
顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！
你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。
我们把桃花岛抽象成了一个图，共 \(n\) 个点代表路的相交处，\(m\) 条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。
你的任务是：把所有不同的路线游览完一共要花多少时间？
输入格式
第一行为 \(5\) 个整数 \(n,m,s,t,t_0\)，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从 \(1\) 到 \(n\)）和你乘船从岛东头到西头一次的时间。
以下 \(m\) 行，每行 \(3\) 个整数 \(x,y,t\)，表示从点 \(x\) 到点 \(y\) 有一条行走耗时为 \(t\) 的路。
每一行的多个数据之间用一个空格隔开。
输出格式
假设总耗时为 \(total\)，则输出 \(total\ \bmod 10000\) 的值（\(total\) 对 \(10000\) 取余）。
样例 #1
样例输入 #1
3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15
样例输出 #1
56
提示
【样例说明】
共有 \(3\) 条路径可以从点 \(1\) 到点 \(3\)，分别是 \(1-2-3\)，\(1-2-3\)，\(1-3\)。
时间计算为：
\((5+7)+7 +(5+10)+7 +(15)=56\)
数据范围
\(2\leq n\leq 10^4\)，\(1\leq m\leq 5\times 10^4\)，\(t\leq 10^4\)，\(t_0\leq 10^4\)。
思路
toposort + DP
数组 cnt 记录到当前点的路径数，数组 dis 记到当前点的所有路径和
从起点开始出发dfs，再利用 toposort 维护先后顺序，同时利用 dp 的思想更新 cnt 和 dis 数组，最终答案即为 $dis[t] + (cnt[t] - 1) \times t_0 $，别忘了取余就行
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 1e4 + 5, inf = 0x3f3f3f3f, mod = 1e4;
ll n, m, s, t, tt, in[maxm], cnt[maxm], dis[maxm];
vector<pll> e[maxm];
void dfs(int u){
for(auto v : e[u]){
dis[v.first] = (dis[v.first] + (dis[u] + cnt[u] * v.second) % mod) % mod;
cnt[v.first] = (cnt[v.first] + cnt[u]) % mod;
-- in[v.first];
if(in[v.first] == 0) dfs(v.first);
}
return ;
}
void solve(){
cin >> n >> m >> s >> t >> tt;
for(int i = 0; i < m; ++ i){
int x, y, z;
cin >> x >> y >> z;
e[x].push_back({y, z});
++ in[y];
}
cnt[s] = 1;
dfs(s);
cout << (dis[t] + (cnt[t] - 1) * tt % mod) % mod << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}