ECNU 3462. 最小 OR 路径 [dfs+枚举]

题意：给你n个点，m条边，起点s与终点e，求s到e的路径最小或和。

题解：从大到小贪心枚举每一个位，看是否能通过不包含这个位的路径到达终点，若能则可以删除这个位的贡献，由于每次dfs只需要遍历所有未到达的边所以，时间复杂度为O（62*（m））。

AC代码：

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
typedef long long ll;
struct node
{
ll v,w,id;
node(){}
node(ll v,ll w,ll id)
{
this->v=v;
this->w=w;
this->id=id;
}
};
vector<node>vt[10005];
ll s,e;
ll mark[1000005];
ll now;
ll dfs(ll u)
{
if(u==e)return 1;
for(ll i=0;i<vt[u].size();i++)
{
ll to=vt[u][i].v;
if(mark[vt[u][i].id]||(now&vt[u][i].w))continue;
mark[vt[u][i].id]=1;
if(dfs(to))return 1;
}
return 0;
}
ll f[65];
int main()
{
f[0]=1;
for(ll i=1;i<=61;i++)f[i]=f[i-1]*2ll;
ll n,m;
scanf("%lld%lld",&n,&m);
ll haha=0;
for(ll i=0;i<m;i++)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
if(u==v)continue;
vt[u].push_back(node(v,w,i+1));
vt[v].push_back(node(u,w,i+1));
haha|=w;
}
scanf("%lld%lld",&s,&e);
now=0;
if(!dfs(s))printf("-1n");
else
{
ll ans=(1ll<<62ll)-1;
for(ll i=61;i>=0;i--)
{
if(!(haha&f[i]))
{
ans-=f[i];
continue;
}
for(ll j=0;j<m;j++)mark[j]=0;
now|=f[i];
if(!dfs(s))now^=f[i];
else ans-=f[i];
}
printf("%lldn",ans);
}
}

最后

以上就是满意世界为你收集整理的ECNU 3462. 最小 OR 路径 [dfs+枚举]的全部内容，希望文章能够帮你解决ECNU 3462. 最小 OR 路径 [dfs+枚举]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。