自动搬运

查看原文

来自洛谷，原作者为

	tjtdrxxz 要是把博士抬去寝室，会不会被人误会啊？干脆就这样子放着好了......？

搬运于2025-08-24 23:02:37，当前版本为作者最后更新于2024-10-16 11:54:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目要求我们建的树满足 $D_i = S_i$，容易想到用其他路径代替最短路中的路径。

例：

很明显，如果两条红边的长等于黑边的长，那么这条黑边就可以被两条红边代替。

所以我们跑一遍最短路，然后 $O (n ^ 2)$ 统计答案。答案就是叶节点到根节点最短路径数量的积。

注意：堆的重载运算符别写错啦。

code：

# include <bits/stdc++.h>
# define int __int128
using namespace std;
int mp[1011][1011];
int n, m;
struct path
{
	int v, w;
	path (int v = 0, int w = 0) :
		v (v), w (w) {}
};
vector <path> e[100012];
int dis[1011];
struct node
{
	int u, w;
	node (int u = 0, int w = 0) :
		u (u), w (w) {}
	bool operator < (const node &b) const
	{
		return w > b.w;
	}
};
priority_queue <node> q;
bool vis[1011];
void dijkstra (int st)
{
	for (int i = 1; i <= n; i ++) dis[i] = 1e18, vis[i] = 0;
	dis[st] = 0;
	q.push (node (st, 0));
	while (not q.empty ())
	{
		int u = q.top ().u;
		q.pop ();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto it : e[u])
		{
			int v = it.v, w = it.w;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push (node (v, dis[v]));
			}
		}
	}
}
# define stdi stdin
# define stdo stdout
int ans = 0;
int mod = (1 << 31) - 1;
signed main()
{
	freopen ("dark.in", "r", stdin);
	freopen ("dark.out", "w", stdout);
	setvbuf (stdi, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
	setvbuf (stdo, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
	memset (mp, 0x3f, sizeof (mp));
	scanf ("%lld %lld", &n, &m);
	for (int i = 1; i <= m; i ++)
	{
		int u, v, w;
		scanf ("%lld %lld %lld", &u, &v, &w);
		e[u].push_back (path (v, w));
		e[v].push_back (path (u, w));
		mp[u][v] = mp[v][u] = min (mp[u][v], w);
	}
	dijkstra (1);
	ans = 1;
	for (int i = 2; i <= n; i ++)
	{
		int sum = 0;
		for (int j = 1; j <= n; j ++)
		{
			sum += ((dis[j] + mp[i][j]) == dis[i]);
		}
		if (sum > 0) ans = (ans * sum) % mod;
	}
	printf ("%lld\n", ans);
}