牛客练习赛67 E 牛妹游历城市
牛妹游历城市
https://ac.nowcoder.com/acm/contest/6885/E
E 牛妹游历城市
题目地址：
基本思路：
比较容易让人想到最短路,
但是如果直接建图跑,很明显会超时,所以我们考虑重新建图,
我们将每一个二进制位设置为个虚点，将所有这一二进制位为
的数都连向这个虚点,
并且将入边的权值设为这个二进制位的基数,出边权值设为,
具体什么意思,我们参考下面的例子:
考虑,
这两个数,它们转换为二进制为：
和
，我们将顶点标下号,
这两个数的点我们设为和
,二进制第一位我们设为
，第二位设为
,依次类推，那么我们有如下这幅图：
(不太会用软件,标上边权就重叠了，所以没弄，可以自己画一下)
然后我们看,,
这两个数字实际上是被二进制第一位和第三位都连着了,
但是由于二进制第一位的边权明显是小于第三位的,那么在实际最短路中,肯定只会走这个更短的边权,
这也就是的效果,那么就能证明这样的建图是正确的了。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
int a[maxn], dis[maxn];
struct edge {
int to, next,w;
}edge[maxn];
int head[maxn], cnt;
void add_edge(int u, int v, int w) {
edge[++cnt] = {v, head[u], w};
head[u] = cnt;
edge[++cnt] = {u, head[v], 0};
head[v] = cnt;
}
int n;
bool vis[maxn];
void dijkstra() {
for (int i = 1; i <= n + 33; i++) dis[i] = INF, vis[i] = false;
dis[1] = 0;
priority_queue<pii, vector<pii >, greater<> > q;
q.push(mp(0, 1));
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].w) {
dis[v] = dis[u] + edge[i].w;
q.push(mp(dis[v], v));
}
}
}
}
signed main() {
int t;
cin >> t;
while (t--) {
cin >> n;
rep(i, 1, n) cin >> a[i];
cnt = 0, mset(head, -1);
for (int i = 0; i < 33; i++) {
for (int j = 1; j <= n; j++) {
if ((a[j] >> i) & 1) {
add_edge(j, i + n + 1, 1ll << i);
}
}
}
dijkstra();
if (dis[n] == INF) cout << "Impossible" << endl;
else cout << dis[n] << endl;
}
return 0;
}
OPPO公司福利 1133人发布