题解：P12780 [ICPC 2024 Yokohama R] Omnes Viae Yokohamam Ducunt?

妙妙推导题。

首先思考假设我们建了一个最小生成树，那么对于任意一条从

i

到首都的路径中的边

e

，如果断开那么

i

绝对到不了首都，所以

i

其实是给任意一条从

i

到首都的路径中的边都增加了

p_i

的“贡献”，所以，题目所求就是（

P(e)

指的是

e

的损失，

C(e)

指的是

e

的脆弱度，

D(i)

指的是从

i

到首都

1

的距离（以脆弱度为边））：

\sum_e P(e) \times C(e)

=\sum_i p_i \times D(i)

等等，这不就是……最短路吗？

是的，于是这道题就没了。

十年 OI 一场空，不开 long long 见祖宗！！

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node
{
	int x;
	long long w;
	bool operator<(const node&a)const
	{
		return w>a.w;
	}
};
int a[N];
vector<node>e[N];
priority_queue<node>q;
long long d[N];
int vis[N];
signed main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		long long z;
		scanf("%d %d %lld",&x,&y,&z);
		e[x].push_back({y,z});
		e[y].push_back({x,z});
	}
	memset(d,0x3f,sizeof(d));
	q.push({1,0});
	d[1] = 0;
	while(q.size())
	{
		int x = q.top().x;
		q.pop();
		if(vis[x])
		{
			continue;
		}
		vis[x] = 1;
		for(node v:e[x])
		{
			if(d[x]+v.w<d[v.x])
			{
				d[v.x] = d[x]+v.w;
				q.push({v.x,d[v.x]});
			}
		}
	}
	long long ans = 0;
	for(int i = 1;i<=n;i++)
    {
        ans+=(long long)a[i]*d[i];
    }
    printf("%lld",ans);
	return 0;
}

题解：P12780 [ICPC 2024 Yokohama R] Omnes Viae Yokohamam Ducunt?

文章操作

相关推荐

评论

题解：P12780 [ICPC 2024 Yokohama R] Omnes Viae Yokohamam Ducunt?