自动搬运

查看原文

来自洛谷，原作者为

	FLY_lai Nijika Ijichi

搬运于2025-08-24 23:11:12，当前版本为作者最后更新于2024-07-12 22:17:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【$n\le 10$】

给爆搜的。不过搜索应该也不好写。

【所有边权相等】

这个题的难点其实就在于有可能通过往回走把原本的下一步变小。但是当所有边权相等的时候，往回走本身就要花费 "原本下一步" 的权值，再走回来必然严格更差。

所以不会走回头路。于是只需要正常跑最短路即可。

【满分做法】

样例二给了提示：$303063652$ 在经过一次变化之后不变。可能会启示选手们思考这个函数本身的不变性质。

观察发现，$\dfrac{1}{1-\dfrac{1}{1-\dfrac{1}{1-x}}}=x$，也就是说一条道路变化三次之后会变成原来的长度。

既然如此，我们直接分层图，将图分成三层。令 $x'=\dfrac{1}{1-x},x''=\dfrac{1}{1-x'}$。

对于一条边 $(u,v,w)$，在新图里变成三条边：$(u_1,v_2,w),(u_2,v_3,w'),(u_3,v_1,w'')$。然后从 $1$ 跑最短路，答案就是 $\min(dist[n_1],dist[n_2],dist[n_3])$。

Fun Facts: 这题本来模数是 $998$，但是我们发现 $998$ 没有一个迭代之后等于自身的不好做提示性样例，所以改了模数。实在太伟大了

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 3e5 + 5;
const ll MOD = 754974721;

ll fpow(ll a, ll b, ll p) {
	ll mul = 1;
	while (b) {
		if (b & 1)
			mul = mul * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return mul;
}
long long inv(long long x, long long mod) { // 计算 x 在模 mod 下的逆元 
	x = (x % mod + mod) % mod;
	return fpow(x, mod - 2, mod);
}

ll n, m;
struct Edge {
	ll to, val;
	Edge(ll t = 0, ll v = 0) {
		to = t, val = v;
	}
};
vector<Edge> e[N];
void addedge(ll u, ll v, ll w) {
	ll ww = inv(1 - w, MOD), www = inv(1 - ww, MOD);
	e[u].push_back(Edge(v + n, w));
	e[u + n].push_back(Edge(v + 2 * n, ww));
	e[u + 2 * n].push_back(Edge(v, www));
	
	e[v].push_back(Edge(u + n, w));
	e[v + n].push_back(Edge(u + 2 * n, ww));
	e[v + 2 * n].push_back(Edge(u, www));
}

ll dist[N];
bool vis[N];
typedef pair<ll, ll> pii;
void dijkstra(ll s) {
	priority_queue<pii, vector<pii>, greater<pii> > q;
	memset(dist, 0x3f, sizeof dist);
	memset(vis, false, sizeof vis);
	dist[s] = 0;
	q.push(make_pair(dist[s], s));
	while (!q.empty()) {
		ll h = q.top().second;
		q.pop();
		if (vis[h])
			continue;
		vis[h] = true;
		for (ll i = 0; i < e[h].size(); i++)
			if (dist[e[h][i].to] > dist[h] + e[h][i].val) {
				dist[e[h][i].to] = dist[h] + e[h][i].val;
				q.push(make_pair(dist[e[h][i].to], e[h][i].to));
			}
	}
}
int main() {
	cin >> n >> m;
	for (ll i = 1; i <= m; i++) {
		ll u, v, w;
		cin >> u >> v >> w;
		addedge(u, v, w);
	}
	dijkstra(1);
	cout << min(dist[n * 3], min(dist[n * 2], dist[n]));
	return 0;
}