首页 > 牛客IOI周赛26-普及组的D题谁能帮我看一下代码为什么90
头像
C++萌新
发布于 2021-06-05 10:49
+ 关注

牛客IOI周赛26-普及组的D题谁能帮我看一下代码为什么90

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f;
const int MAXN = 1e7 + 100;
const double eps = 1e-6;
const int N = 1e5;
ll Data[MAXN];
int head[MAXN];
ll dis[MAXN];
int vis[MAXN];
int cnt;
struct T{
    int id;
    int dis;
	bool operator < (const T &a) const{
		return a.dis < dis;
	}
};
struct Edge{
    int next;
    int to;
    ll value;
}edge[MAXN];
void Add_Edge(int u, int v, ll val){
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].value = val;
    head[u] = cnt++;
}
priority_queue<T> q;
void dijstra(int s){
    dis[s] = 0;
    T now;
    now.dis = dis[s];
    now.id = s;
    q.push(now);
    while(!q.empty()){
        T u = q.top();
        q.pop();
        if(vis[u.id]) continue;
        vis[u.id] = 1;
        for(int i=head[u.id];i!=-1;i=edge[i].next){
            if(!vis[edge[i].to] && dis[edge[i].to] > edge[i].value + dis[u.id]){
                dis[edge[i].to] = edge[i].value + dis[u.id];
                now.id = edge[i].to;
                now.dis = dis[edge[i].to];
                q.push(now);
            }
        }
    }
}
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    scanf("%d", &n);
    memset(head, -1, sizeof head);
    memset(dis, 0x3f, sizeof dis);
    for(int i=0;i<n;i++) {
        scanf("%lld", Data + i);
        for(int j=0;j<31;j++){
            if(Data[i] >> j & 1){
                Add_Edge(i, n + j + 1, Data[i]);
                Add_Edge(n + j + 1, i, Data[i]);
            }
        }
    }
    dijstra(0);
    for(int i=0;i<n;i++){
        if(dis[i] == 0x3f3f3f3f3f3f3f3f) cout << -1 << " ";
        else cout << dis[i] << " ";
    }
    return 0;
}


全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐