做法:
把二进制中的每一位看作是一个点,改位为1就建立长度为的边
跑dij即可
代码
// Problem: 最短路 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11233/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<ll,int> PII; typedef unsigned long long ull; typedef long double ld; const int N=100040; const ll INF=1e18; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); struct edge{ int to; //连接的节点 ll cost; //边长 }; vector<edge> g[N]; ll dis[N]; bool vis[N]; int n; void init(){ for(int i=1;i<=n+30;i++) dis[i]=INF; dis[0]=0; } void Dijkstra(){ init(); priority_queue<PII,vector<PII>,greater<PII> > que; //按first从小到大 que.push({0,0}); while(!que.empty()){ auto t=que.top();que.pop(); int v=t.second; // if(dis[v]<t.first) continue; if(vis[v]) continue; vis[v]=1; for(int i=0;i<g[v].size();i++){ auto e=g[v][i]; if(dis[e.to] > dis[v]+e.cost){ dis[e.to] = dis[v]+e.cost; que.push({dis[e.to],e.to}); } } } } void solve(){ cin>>n; rep(i,0,n-1){ ll x;cin>>x; for(int j=0;j<=30;j++){ if((x>>j)&1){ g[i].pb({n+j,x}); g[n+j].pb({i,x}); } } } Dijkstra(); rep(i,0,n-1){ if(dis[i]!=INF) cout<<dis[i]<<" \n"[i==n-1]; else cout<<-1<<" \n"[i==n-1]; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }