拆位+堆优化最短路牛妹游历城市牛客练习赛67 最短路

对于一道题目，如果涉及到了位运算，二进制，那么优先考虑二进制，观察其性质
本题以对点权的二进制构造边，构造32个虚点，从而建立出图

堆优化优先队列，一定不要出现爆LL的情况，这样极有可能MLE，TLE，因为入队次数会变得乱糟糟的

//#define LOCAL #include using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f7f7f7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0)template void read(T &x) {x = 0; char ch = getchar(); ll f = 1; while(!isdigit(ch)){if(ch == '-')f *= -1; ch = getchar(); }while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar(); }x *= f; } template void read(T &first, Args& ... args) {read(first); read(args...); } template void write(T arg) {T x = arg; if(x < 0) {putchar('-'); x =- x; }if(x > 9) {write(x / 10); }putchar(x % 10 + '0'); } template void write(T arg, Ts ... args) {write(arg); if(sizeof...(args) != 0) {putchar(' '); write(args ...); }} using namespace std; const int N = 1e5 + 100; const int M = 6400050; const ll MAXN = (1ll << 32); int n ; int head[N], cnt; ll val[N]; struct node1 { int t, next; ll w; }edge[M]; void add (int f, int t, ll w) { edge[cnt].w = w; edge[cnt].t = t; edge[cnt].next = head[f]; head[f] = cnt ++; } struct node { int v; ll value; node(int a, ll b):v(a),value(b){}; bool operator < (const node& no) const { return value > no.value; } }; ll dis[N]; void dijkstra(int s) { for (int i = 0 ; i <= n + 40 ; i ++) dis[i] = 1e18; p_queue q; dis[s] = 0; q.push(node(s,0)); while(!q.empty()) { node no = q.top(); q.pop(); int u = no.v; for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].t; ll w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.push(node(v,dis[v])); } } } } int main() { cout << (1 << 32) << endl; int T; read (T); while (T --) { read (n); cnt = 0; for (int i = 1 ; i <= n + 40 ; i ++) head[i] = -1; for (int i = 1 ; i <= n ; i ++) read (val[i]); int p = n; for (ll t = 1 ; t < MAXN ; t <<= 1) { ++ p; for (int i = 1 ; i <= n ; i ++) { if(val[i] & t) { add (i , p , t); add (p , i, 0); } } } dijkstra(1); if(dis[n] == 1e18) printf("Impossible\n"); else write(dis[n]), LF; }} /* 2 6 5 0 1 0 1 0 1 1 3 3 5 1 2 2 4 4 5 */

【拆位+堆优化最短路牛妹游历城市牛客练习赛67】