首页 > 小苯的最短路

天鹅Swan

发表于 2024-12-01 21:10:00

更好的阅读体验可看CSDN 思路用dijkstra写一个打表，打表代码 #include <bits/stdc++.h> #define maxOf(a) *max_element(a.begin(),a.end()) #define minOf(a) *min_element(a.b 展开全文

yunayu

发表于 2026-01-28 01:31:13

猜的。好了不开玩笑了。分析题目，可得任意两点间XOR下路径长度都不会小于它们XOR的结果。这是一个很显然的结果，因为XOR在位与位之间是独立的，且其定义为相同记为0，不同记为1。在本题中值相同的位显然已经最优了，不用考虑。考虑值不同的位(0/1或1/0)，我们不可能找到一个中间值使得这个代价在传递中展开全文

Turgen

发表于 2026-01-28 01:36:55

思路：看一眼数据，回答最多，但很显然这题要求我们用，也就是推一个式子。由于必须O(1)回答，所以对于1到j的最短路径，一定是直接边结论1：两个不同的正整数异或结果一定非负，既。已知可以让原本偶数+1，奇数-1,假设有中间转点k，则其路径至少是。若，也就是至少，容易发现无论j是奇数还是偶数，都不比这展开全文

此在Dasein

发表于 2026-01-28 07:21:02

1. 问题分析题目给出了一个个点的无向完全图（Complete Graph），任意两点之间的边权定义为（按位异或）。目标是计算起点到所有点 () 的最短路长度的异或和，即。数据组数。由于高达，这直接否定了任何、甚至的算法。标准的图论算法（如 Dijks 展开全文

2025112525

发表于 2026-01-28 19:31:06

#include <iostream> using namespace std; typedef long long LL; int main() { LL t; cin >> t; LL n; for (int i = 0; i < 展开全文

Yuaeb_698

发表于 2026-01-28 00:29:09

不用dijkstra也可以打表。最短路不必用dijkstra推出来，肯定是1直接走到n，这样二进制变化肯定是最少的（反正到最后肯定要变嘛）。然后再做一个前缀异或和，就可以打表了。不过，不打表直接推也行。相邻的偶数和奇数，2k与2k+1的异或和肯定是1。1->2 边权31->3 边权21- 展开全文

小男娘

发表于 2026-01-28 00:35:55

如标题所示，考虑路径长度的异或和，路径中间节点的异或全都被消掉，于是其等于一条边路径的异或和。考虑到一大堆数求和一定大于等于其异或和，于是最短路就是一条边路径。于是题目变成了求。先求，发现四个一组异或和为零可以直接消掉，于是答案就只剩下四种情况，分别求即可 #include <iostream 展开全文

czw9527

发表于 2026-01-28 10:31:28

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () = 展开全文

YunBaichuan

发表于 2026-01-28 10:46:55

思路：思维。首先我们要知道1到其他点的最短路径是什么？由于题目说了是无向完全图，即每个点都能直达另一个点，所以说直达可能是最短路径。假设直达不是最短路径，说明真正的最短路径之间会经过一些点，那么经过这些点的权重就是(a ^ b) + (b ^ c) + (c ^ d)....根据异或的性质，直达最短展开全文

BeauWill

发表于 2026-01-28 10:54:34

#include <iostream> #include <vector> #include <queue> #include <array> void solve(){ int n; std::cin >> n; if(n 展开全文

查看本题

查看本题讨论

等你来战

查看全部

牛客小白月赛129

报名截止时间：2026-02-27 21:00
牛客周赛 Round 133

报名截止时间：2026-03-01 21:00

相关比赛

等你来战