游览

链接

直接遍历所有肯定不可行
我们可以尝试dp ,设cnt[i]表示到达i节点的路径数量,sum[i]表示到达路径i所需的时间
那么,对于u->v,代价为w,我们可以得到cnt[v]=cnt[v]+cnt[u]
sum[v]=sum[v]+sum[u]+cnt[u]*w

由于u-v有cnt[u]种方式,所以cnt[u]*w 而不是cnt[v]*w

经测试,这题没有多起点的情况,不需要考虑

代码如下:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int mod = 10000;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, s, t0, t1;
	cin >> n >> m >> s >> t0 >> t1;
	vector<vector<pair<int, int>>>adj(n + 1);
	vector<int>inge(n + 1, 0);
	for (int i = 0;i < m;i++) {
		int x, y, w;
		cin >> x >> y >> w;
		adj[x].push_back({ y,w });
		inge[y]++;
	}
	queue<int>q;
	for (int i = 1;i <= n;i++) {
		if (!inge[i]) q.push(i);
	}
	vector<int>topo;
	topo.reserve(n);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		topo.push_back(cur);
		for (auto nt : adj[cur]) {
			if (--inge[nt.first]==0) q.push(nt.first);
		}
	}
	vector<int>cnt(n + 1, 0), sum(n + 1, 0);
	cnt[s] = 1;
	for (int i = 0;i < topo.size();i++) {
		int u = topo[i];
		//if (cnt[u] == 0) continue;
		for (auto it : adj[u]) {
			int v = it.first;
			int w = it.second;
			cnt[v] = (cnt[u] + cnt[v]) % mod;
			sum[v] = (sum[u] + sum[v] + cnt[u] * w) % mod;
		}
	}
	int ans = 0;
	int Sum = sum[t0], total_cnt = cnt[t0];
	total_cnt = (total_cnt - 1 + mod) % mod;
	ans = (Sum + total_cnt * t1) % mod;
	cout << ans;
	
}

要注意注释代码原意是忽略多起点的情况,但可能cnt[u]=10000取模变成0的情况导致出错

如果要规避多起点的情况可以直接从s开始(应该?)

时间复杂度:O(n+m)

空间复杂度:O(n+m)