本文共 2574 字，大约阅读时间需要 8 分钟。
Cicasso计划进行一场四城市的世界巡游，他希望这段旅程的总距离尽可能长。为了实现这一目标，我们需要选择四个不同的城市，并确定一个顺序，使得从第一个到第二个、第二个到第三个、第三个到第四个的每一步都是该城市对之间的最短路径。总距离将是这些路径之和，我们的目标是找到这个总距离的最大值。
#includeusing namespace std;#define INF 0x3f3f3f3f#define MOD 1000000007int n, m;vector > edge(n + 1);int dis[n + 1][n + 1];pii shun[n + 1][4];pii ni[n + 1][4];void updates(int u, int v) { shun[u][3] = shun[u][2]; shun[u][2] = shun[u][1]; shun[u][1] = make_pair(v, dis[u][v]);}void updaten(int u, int v) { int t = dis[u][v]; if (t > ni[v][1].second) { ni[v][3] = ni[v][2]; ni[v][2] = ni[v][1]; ni[v][1] = make_pair(u, dis[u][v]); } else if (t > ni[v][2].second) { ni[v][3] = ni[v][2]; ni[v][2] = make_pair(u, dis[u][v]); } else if (t > ni[v][3].second) { ni[v][3] = make_pair(u, dis[u][v]); }}void bfs(int st) { int vis[n + 1]; memset(vis, 0, sizeof(vis)); dis[st][st] = 0; queue q; q.push(st); while (!q.empty()) { int v = q.front(); q.pop(); vis[v] = 1; for (int i = 0; i < edge[v].size(); ++i) { int u = edge[v][i]; if (vis[u]) continue; dis[st][u] = dis[st][v] + 1; updates(st, u); vis[u] = 1; q.push(u); } }}void main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; edge[u].push_back(v); } for (int i = 1; i <= n; ++i) { bfs(i); } int max_total = -1; int a, b, c, d; for (int u = 1; u <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) continue; for (int k = 1; k <= 3; ++k) { for (int l = 1; l <= 3; ++l) { if (!check(u, j, k, l)) continue; int total = dis[u][j] + ni[u][k].second + shun[j][l].second; if (total > max_total) { max_total = total; a = ni[u][k].first; b = u; c = j; d = shun[j][l].first; } } } } } printf("%d %d %d %d\n", a, b, c, d);}
bfs 使用广度优先搜索来计算从起点到其他所有节点的最短距离，并更新相关的前三最远节点。这个方法确保了我们能够在合理的时间内找到满足条件的最长路径，确保Cicasso的世界巡游既有趣又尽可能漫长。
转载地址：http://hzkiz.baihongyu.com/