Problem - D - Codeforces

?

Chouti已經(jīng)厭倦了乏味的作業(yè)，于是他打開(kāi)了數(shù)年前創(chuàng)建的一個(gè)舊編程問(wèn)題。

給定一個(gè)具有n個(gè)節(jié)點(diǎn)和m條加權(quán)邊的連通無(wú)向圖。其中有k個(gè)特殊節(jié)點(diǎn)：x1,x2,...,xk。

現(xiàn)在定義路徑的成本為其邊權(quán)的最大值。兩個(gè)頂點(diǎn)之間的距離定義為連接它們的路徑的最小成本。

對(duì)于每個(gè)特殊節(jié)點(diǎn)，請(qǐng)找到與其距離最遠(yuǎn)（根據(jù)上述定義，即相應(yīng)距離是可能的最大值）的另一個(gè)特殊節(jié)點(diǎn)，并輸出它們之間的距離。

由于原始限制非常小，所以他認(rèn)為這個(gè)問(wèn)題很無(wú)聊?，F(xiàn)在，他提高了限制，并希望您能為他解決這個(gè)問(wèn)題。

輸入 第一行包含三個(gè)整數(shù)n、m和k（2≤k≤n≤105，n?1≤m≤105）——節(jié)點(diǎn)數(shù)、邊數(shù)和特殊節(jié)點(diǎn)數(shù)。

第二行包含k個(gè)不同的整數(shù)x1,x2,…,xk（1≤xi≤n）。

接下來(lái)的m行，每行包含三個(gè)整數(shù)u、v和w（1≤u,v≤n，1≤w≤109），表示存在一條權(quán)值為w的邊連接u和v。給定的圖是無(wú)向的，因此邊（u，v）可以在兩個(gè)方向上使用。

圖可能有多條邊和自環(huán)。

保證圖是連通的。

輸出 第一行應(yīng)包含k個(gè)整數(shù)。第i個(gè)整數(shù)是xi與離它最遠(yuǎn)的特殊節(jié)點(diǎn)之間的距離。

Examples

input

Copy

2 3 2
2 1
1 2 3
1 2 2
2 2 1

output

Copy

2 2 

input

Copy

4 5 3
1 2 3
1 2 5
4 2 1
2 3 2
1 4 4
1 3 3

output

Copy

3 3 3 

在第一個(gè)例子中，頂點(diǎn) 1 和頂點(diǎn) 2 之間的距離等于 2，因?yàn)樗鼈冎g有一條權(quán)重為 2 的邊。因此，對(duì)于頂點(diǎn) 1 和頂點(diǎn) 2 來(lái)說(shuō)，到最遠(yuǎn)節(jié)點(diǎn)的距離都是 2。

在第二個(gè)例子中，可以發(fā)現(xiàn)頂點(diǎn) 1 和頂點(diǎn) 2 之間、頂點(diǎn) 1 和頂點(diǎn) 3 之間的距離都是 3，而頂點(diǎn) 2 和頂點(diǎn) 3 之間的距離是 2。

該圖可能存在多個(gè)邊和自環(huán)，如第一個(gè)例子所示。

題解:
由于我們找的是特殊節(jié)點(diǎn)之間的最短距離,這道題比較特殊的是兩點(diǎn)間的路徑長(zhǎng)度為,中間遍歷過(guò)的最大邊權(quán)值

由于題中兩點(diǎn)距離是最小成本,相當(dāng)于兩點(diǎn)最小的路徑長(zhǎng)度,既然求的最小我們可以先利用最小生成樹(shù),把不需要的邊去掉,這樣一定最優(yōu)

現(xiàn)在就變成了一棵樹(shù)了,那么從任意一個(gè)特殊點(diǎn)開(kāi)始,到其他所有特殊點(diǎn),中途遍歷過(guò)最長(zhǎng)的邊權(quán),就是

離它最遠(yuǎn)的特殊節(jié)點(diǎn)之間的距離

這個(gè)距離對(duì)于所有特殊點(diǎn),都適用

因?yàn)槲覀兪菑囊粋€(gè)特殊點(diǎn)開(kāi)始的,我們找的這個(gè)最長(zhǎng)邊權(quán)的兩側(cè),肯定都有特殊點(diǎn),這樣兩邊的點(diǎn)都可以經(jīng)過(guò)這個(gè)最長(zhǎng)邊權(quán)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-428476.html

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 998244353;
int n,m,k;
struct node
{
	int l,r,x;
}a[100050];
int b[100050];
int f[100050];
int cmp(node a,node b)
{
	return a.x < b .x;
}
int find(int x)
{
	if(f[x] == x)
	return x;
	return f[x] = find(f[x]);
}
vector<PII> p[100050];
int d[100050];
void dfs(int x,int fa)
{
	for(PII ne:p[x])
	{
		if(ne.first == fa)
		continue;
		d[ne.first] = max(d[x],ne.second);
		dfs(ne.first,x);
	}
}
void solve()
{
	cin >> n >> m >> k;
	for(int i = 1;i <= k;i++)
	{
		cin >> b[i];
	}
	for(int i = 1;i <= m;i++)
	{
		cin >> a[i].l >> a[i].r >> a[i].x; 
	}
	for(int i = 1;i <= n;i++)
	f[i] = i; 
	sort(a + 1,a + 1 + m,cmp);
	for(int i = 1;i <= m;i++)
	{
		int x = find(a[i].l);
		int y = find(a[i].r);
		if(x != y)
		{
			f[x] = y;
			p[a[i].l].push_back({a[i].r,a[i].x});
			p[a[i].r].push_back({a[i].l,a[i].x});
		}
	}
	dfs(b[1],0);
	int ma = 0;
	for(int i = 1;i <= k;i++)
	ma = max(ma,d[b[i]]);
	for(int i = 1;i <= k;i++)
	cout << ma <<" ";
}
//5 7 8 9 10

signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve(); 
	}
}

到了這里，關(guān)于D. Maximum Distance(最小生成樹(shù))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！