题意:给你n个点,m条边,起点s与终点e,求s到e的路径最小或和。
题解:从大到小贪心枚举每一个位,看是否能通过不包含这个位的路径到达终点,若能则可以删除这个位的贡献,由于每次dfs只需要遍历所有未到达的边所以,时间复杂度为O(62*(m))。
AC代码:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复