HDU - 6713 最短路1（思维）

39 阅读 0 评论 26 点赞

我是靠谱客的博主犹豫心锁，最近开发中收集的这篇文章主要介绍HDU - 6713 最短路1（思维），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意

题目链接

有一张 n 个点的完全无向图，点的标号是 1…n，其中边 (i,j) 的长度是 i xor j，现在你需要求出点 1 到点 n 的最短路的长度。

分析

异或的特殊性，从1 到 n 不论怎么走，路径的最后一步，即某个点 x 到 n 点的距离是 1 ^ n，让1 ~ n 的路径最小那就让 x为1 就好了。

AC代码


#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define eps 1e-8
typedef long long ll;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t, n;
std::cin >> t;
while(t--){
std::cin >> n;
int x = (1 ^ n);
std::cout << x << "n";
}
return 0;
}