bfs+枚举，CF666B - World Tour

本文主要是介绍bfs+枚举，CF666B - World Tour，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 666B - Codeforces

---

二、解题报告

1、思路分析

数据量允许跑N次bfs预处理所有点的最短路，以及预处理到达每个点距离最远的3个点，以及每个点能够到达的最远的3个点

我们枚举<b, c>，然后枚举 到达b的最远点a，c能到达的最远点d，由于存了前三个最远的所以一定能找到4个不一样的a，b，c，d

维护答案输出即可

写py是因为太晚了懒得敲cpp（逃

2、复杂度

时间复杂度： O((N + M) * M)空间复杂度：O(N*N)

3、代码详解

 ​

N, M = map(int, input().split())g = [[] for _ in range(N)]for _ in range(M):u, v = map(int, input().split())u -= 1v -= 1g[u].append(v)def get(x: int, y: int) -> int:return x * N + ydst = [-1] * (N * N)
ma = [[-1] * 3 for _ in range(N)]
ma_rev = [[-1] * 3 for _ in range(N)]
q = [0] * Nfor i in range(N):dst[get(i, i)] = 0q[0] = if, b = 0, 1while b - f:u = q[f]f += 1for v in g[u]:if dst[get(i, v)] == -1:dst[get(i, v)] = dst[get(i, u)] + 1q[b] = vb += 1for i in range(N):for j in range(N):if dst[get(i, j)] > 0:if ma[i][0] == -1 or dst[get(i, j)] >= dst[get(i, ma[i][0])]:ma[i][0], ma[i][1], ma[i][2] = j, ma[i][0], ma[i][1]elif ma[i][1] == -1 or dst[get(i, j)] >= dst[get(i, ma[i][1])]:ma[i][1], ma[i][2] = j, ma[i][1]elif ma[i][2] == -1 or dst[get(i, j)] >= dst[get(i, ma[i][2])]:ma[i][2] = jfor i in range(N):for j in range(N):if dst[get(i, j)] > 0:if ma_rev[j][0] == -1 or dst[get(i, j)] >= dst[get(ma_rev[j][0], j)]:ma_rev[j][0], ma_rev[j][1], ma_rev[j][2] = i, ma_rev[j][0], ma_rev[j][1]elif ma[i][1] == -1 or dst[get(i, j)] >= dst[get(ma_rev[j][1], j)]:ma_rev[j][1], ma_rev[j][2] = i, ma_rev[j][1]elif ma[i][2] == -1 or dst[get(i, j)] >= dst[get(ma_rev[j][2], j)]:ma_rev[j][2] = ires = 0
ans = []for b in range(N):for c in range(N):if dst[get(b, c)] <= 0:continuefor i in range(3):a = ma_rev[b][i]if ~a and a != b and a != c:for j in range(3):d = ma[c][j]if ~d and a != d and b != d and c != d:t = dst[get(a, b)] + dst[get(b, c)] + dst[get(c, d)]if t > res:ans = [a, b, c, d]res = t
print(' '.join(str(x + 1) for x in ans))

这篇关于bfs+枚举，CF666B - World Tour的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---