牛客-小a与星际探索

这是一道伪图论题

链接：https://ac.nowcoder.com/acm/problem/22144
来源：牛客网

题目描述

小a正在玩一款星际探索游戏，小a需要驾驶着飞船从11号星球出发前往nn号星球。其中每个星球有一个能量指数pp。星球ii能到达星球jj当且仅当pi>pjpi>pj。
同时小a的飞船还有一个耐久度tt，初始时为11号点的能量指数，若小a前往星球jj，那么飞船的耐久度会变为t⊕pjt⊕pj(即tt异或pjpj，关于其定义请自行百度)
小a想知道到达nn号星球时耐久度最大为多少

注意：对于每个位置来说，从它出发可以到达的位置仅与两者的pp有关，与下标无关

输入描述:

第一行一个整数nn，表示星球数
接下来一行有nn个整数，第ii个整数表示pipi

输出描述:

一个整数表示到达nn号星球时最大的耐久度
若不能到达nn号星球或到达时的最大耐久度为00则输出−1−1

为什么说这是一道伪图论题呢？因为我是按图论做的，我起初认为这是之前总结的最短路。但不过发现这不满足最短路的性质，因为 if-a<b,a^c<b^c不一定成立。所以我们不能按照最短路的方法(也就是每次选择一个异或最大的点)，只能把每一条路(可以到达n的)，所有可能值找出一个最大值。【其实就是动态规划的思想，但我水平比较渣到现在也没能理解透动态规划，就先按图论做的】

难点：他每进入一个星球，对应的耐久度会变，但是有不同的路径进入这个星球，也就是说进入这个星球是的耐久度不确定，所以不能用dis数组记录了。我们在这里不免会把它所有的进入这个星球时的耐久度记录，然后再从每个耐久度开始继续往下进行。这就把所有可能走完了。其实这就是BFS【宽度优先搜索】的原理了。

以下是BFS的代码： 时间复杂度 O(n^2)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstring>
#include<queue>
typedef unsigned long long ll;
const int INF=1e9;
const int maxn=1e6+5;
using namespace std;
int vis[maxn];
int save[maxn];
int ans=0;
void BFS(int n)
{
    memset(vis,false,sizeof(vis));
    queue<int>q;
    q.push(save[1]);
    while(!q.empty())
    {
        int pre=q.front();
        q.pop();
        for(int i=2;i<=n;i++)//遍历走2-n的点随便走。
        {
            if(save[i]<pre)//当前耐久度大于下一个要去的星球就去
            {
                if(i==n) ans=max(ans,save[i]^pre);//每一次到达n，都进行储存比较
                if(i<n&&vis[save[i]^pre]==false)
                {
                    vis[save[i]^pre]=true;
                    q.push(save[i]^pre);//把所有的耐久度可能都进入队列继续搜索
                }
            }
        }
    }

}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        ans=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&save[i]);
        BFS(n);
        printf("%d\n",ans>0?ans:-1);
    }
    return 0;
}