题解：P11321 [NOISG 2020 Qualification] Relay Marathon

Solution

先考虑子任务

3

怎么做。首先路径

1\to 2

必选，只需要考虑剩下的关键点中选择哪两个。

对剩下的关键点跑多源最短路。由超级源点对关键点连边权为

0

的边，跑 dijkstra。于是我们就能得到每个点

u

离最近关键点的距离

dis_u

，也能得到每个点的最近关键点

b_u

，或者说，这个图被分成若干个块，每个块对应一个关键点，块内的点都距离这个关键点最近。

考虑最近的两个关键点之间的路径一定经过两个块的交界处，所以枚举边

i

，满足

b_{u_i} \ne b_{v_i}

，求

dis_{u_i}+dis_{v_i}

的最小值。

考虑两对点怎么做。易证答案中的四个点中，必然有两个是距离最近的（或者你可以理解为就是子任务

3

求得的点），所以我们有两种思路，一种是两个距离最近的关键点连一条边，剩下两个距离次近的再连一条边，这可以仿照子任务

3

求出；另一种是两个距离最近的关键点分别找一个关键点连边，找到两个关键点距离最近的两个点，简单枚举即可。

时间复杂度在 Dijkstra 和排序，为

O(n\log n)

。

Code

CPP

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5,S = 2e5+4;
int n,m,k,a[N],dis[5][N],pre[N],u[3000005],v[3000005],w[3000005],x,y,mmin=999999999,book[N];
bool vis[5][N];
struct node
{
	int v,w;
};
vector<node>vec[N];
priority_queue<PII,vector<PII>,greater<PII>>q;
PII o[N],p[N];
void dijkstra(int u,int k)
{
	memset(dis[k],0x3f,sizeof dis[k]);
	q.push({0,u});
	dis[k][u] = 0;
	while (!q.empty())
	{
		PII now = q.top();
		q.pop();
		if (vis[k][now.second]) continue;
		vis[k][now.second] = 1;
		for (node i: vec[now.second])
		{
			if (dis[k][i.v] > dis[k][now.second]+i.w)
			{
				dis[k][i.v] = dis[k][now.second]+i.w;
				
				if (now.second == S) pre[i.v] = i.v;
				else pre[i.v] = pre[now.second];
				q.push({dis[k][i.v],i.v});
			}
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)
	{
		cin >> u[i] >> v[i] >> w[i];
		vec[u[i]].push_back({v[i],w[i]});
		vec[v[i]].push_back({u[i],w[i]});
	}
	for (int i = 1; i <= k; i++)
	{
		cin >> a[i];
		book[a[i]] = 1;
		vec[S].push_back({a[i],0});
	}
	dijkstra(S,0);
	for (int i = 1; i <= m; i++)
		if (pre[u[i]] != pre[v[i]] && dis[0][u[i]]+dis[0][v[i]]+w[i] < mmin)
			mmin = dis[0][u[i]]+dis[0][v[i]]+w[i],x = pre[u[i]],y = pre[v[i]];
//	cout << x << ' ' << y << ' ' << mmin << '\n';
	dijkstra(x,1);
	dijkstra(y,2);
	int ans = 999999999;
	int cnt1 = 0,cnt2 = 0;
	for (int i = 1; i <= n; i++)
		if (book[i]) o[++cnt1] = {dis[1][i],i};
	sort(o+1,o+cnt1+1);
	for (int i = 1; i <= n; i++)
		if (book[i]) p[++cnt2] = {dis[2][i],i};
	sort(p+1,p+cnt2+1);
	if (cnt1 >= 4)
	{
		if (o[3].second == p[3].second) ans = min(o[3].first+p[4].first,o[4].first+p[3].first);
		else ans = o[3].first+p[3].first;
	}
	for (int i = 0; i < vec[S].size(); i++)
		if (vec[S][i].v == x || vec[S][i].v == y) vec[S][i].w = 999999999;
	dijkstra(S,3);
	int min1 = 999999999;
	for (int i = 1; i <= m; i++)
		if (pre[u[i]] != pre[v[i]] && dis[3][u[i]]+dis[3][v[i]]+w[i] < min1)
			min1 = dis[3][u[i]]+dis[3][v[i]]+w[i];
	cout << min(ans,mmin+min1);
	return 0;
}

题解：P11321 [NOISG 2020 Qualification] Relay Marathon

文章操作

Solution

Code

相关推荐

评论

题解：P11321 [NOISG 2020 Qualification] Relay Marathon