Memory limit:
512 megabytes
给定一个有
n
个点和
m
条边的无向图，其中每一条边
e
i
都有一个权值记为
w
i
。
对于给出的两个点
a
和
b
，求一条
a
到
b
的路径，使得路径上的边权的 OR（位或）和最小，输出这个值。(也就是说，如果将路径看做边的集合
{
e
1
,
e
2
,
…
,
e
k
}
，那么这条路径的代价为
w
1
O
R
w
2
O
R
…
O
R
w
k
，现在求一条路径使得其代价最小，输出这个代价。) 如果不存在这样的路径，输出
−
1
。
Input
第一行两个数
n
和
m
。
接下来
m
行，每行三个数
u
i
,
v
i
,
w
i
，表示有一条
u
i
到
v
i
的权值为
w
i
的无向边。
最后一行两个数
a
,
b
，分别表示起点和终点。
-
2
≤
n
≤
10
3
,
0
≤
m
≤
10
4
,
0
≤
c
i
≤
2
10
−
1
-
1
≤
u
i
,
v
i
,
a
,
b
≤
n
,
a
≠
b
可能有重边和自环。
Output
在一行中输出一个最小代价，如果无解输出
−
1
。
Examples
3 4 1 2 2 1 2 4 1 3 5 2 3 3 1 2
2
Note
图中可能会有重边。
用DFS。
建图的时候一开始用的邻接表，结果我们在枚举某个点指向的各个点时，我们还需要两者之间边的信息（w）。用邻接表只能获得点，所以不行。
而数组也更不可以，因为有重边。
所以用 vector< pair<int,int> >Edge[n+1]; 来存放。可以获得点和边的信息。
建立一个vis【a】【b】，记录到达a点时，代价为b是否存在。
利用bfs，建立两个queue，一个存放点（当前到达了那个点），一个存放代价（到达当前点是的代价为多少）。
我们遍历下一个点，vis[a][b|w]=1。不管三七二十一把所有的情况都遍历完。
之后我们代价从1-1024开始枚举。
找最小代价，也就是到达vis[b][i]。如果存在，那么输出i，break即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
bool vis[1100][1100];
cin>>n>>m;
vector< pair<int,int> >Edge[n+1];
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
Edge[a].push_back(make_pair(b,c));
Edge[b].push_back(make_pair(a,c));
}
int a,b;
cin>>a>>b;
memset(vis,false,sizeof(vis));
vis[a][0]=true;
queue<int>que1;
queue<int>que2;
que1.push(a);
que2.push(0);
while(!que1.empty())
{
int qu1=que1.front();
int qu2=que2.front();
que1.pop();
que2.pop();
for(pair<int,int>b:Edge[a])
{
pair<int,int>dangqian=b;
if(!vis[dangqian.first][qu2|dangqian.second])
{
vis[dangqian.first][qu2|dangqian.second]=true;
que1.push(dangqian.first);
que2.push(dangqian.second|qu2);
}
}
}
int flag=0;
for(int i=1;i<=n;i++)
{
if(vis[b][i])
{
cout<<i<<endl;
flag=1;
break;
}
}
if(flag)
{
}
else
{
cout<<“-1″<<endl;
}
}