首页 > 牛客IOI周赛26普及组D题求助

牛客IOI周赛26普及组D题求助

为什么47行代码初始化改为[1,n+n]就过不了呢
// Problem: 最短路
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11233/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Author:  
//
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef unsigned long long ull;

const long long INF = 1e18;
const int maxn = 2e6+ 7;
const ll mod = 1e9 + 7;

#define pb push_back
#define debug(x) cout << #x << ":" << x << endl;
#define mst(x, a) memset(x, a, sizeof(x))
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define dep(i, a, b) for (ll i = (a); i >= (b); --i)


ll n, a[maxn], dist[maxn], vis[maxn];
vector<PII> v[maxn];

void D() {
    rep(i, 1, n+555) dist[i] = 1e18;
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    while (q.size()) {
        PII fr = q.top();
        q.pop();
        ll u = fr.second;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto f : v[u]) {
            if (dist[f.first] > dist[u] + f.second) {
                dist[f.first] = dist[u] + f.second;
                q.push({dist[f.first], f.first});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;

    rep(i, 1, n) cin >> a[i];

    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= 32; j++) {
            if ((a[i]>>j) & 1ll) {
                v[i].pb({j + n + 1, a[i]});
                v[j + n + 1].pb({i, a[i]});
            }
        }
    }

    D();
    rep(i, 1, n) {
        if (dist[i] >= 1e18)
            dist[i] = -1;
            cout << dist[i] << " ";
    }

    return 0;
}


/*


*/



全部评论

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

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐