Submission #122453

#	Time	Username	Problem	Language	Result	Execution time	Memory
122453		popovicirobert	Price List (POI13_cen)	C++14	30 / 100	193 ms	65536 KiB

cen

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

/*
const int MOD = ;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}


inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}
*/

using namespace std;

const int MAXN = (int) 1e5;

vector <int> g[MAXN + 1];
ll dst[MAXN + 1];

vector < pair <int, int> > G[MAXN + 1];
bool vis[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, k, a, b;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> k >> a >> b;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    memset(dst, 0x3f, sizeof(dst));

    if(a <= b) {
        queue <int> Q;
        Q.push(k);
        dst[k] = 0;

        while(Q.size()) {
            int nod = Q.front();
            Q.pop();

            for(auto it : g[nod]) {
                if(dst[it] > dst[nod] + 1) {
                    dst[it] = dst[nod] + 1;
                    Q.push(it);
                }
            }
        }

        for(i = 1; i <= n; i++) {
            cout << 1LL * min(2 * a, b) * (dst[i] / 2) + (dst[i] & 1) * a << "\n";
        }
        return 0;
    }

    for(int nod = 1; nod <= n; nod++) {
        for(auto it : g[nod]) {
            G[nod].push_back({it, a});
            vis[it] = 1;
        }

        for(auto it : g[nod]) {
            for(auto itr : g[it]) {
                if(vis[itr] == 0) {
                    G[nod].push_back({itr, b});
                }
            }
        }

        for(auto it : g[nod]) {
            vis[it] = 0;
        }
    }

    priority_queue < pair <ll, int> > pq;
    pq.push({0, k});

    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();

        if(vis[cur.second]) {
            continue;
        }

        vis[cur.second] = 1;
        dst[cur.second] = -cur.first;

        for(auto it : G[cur.second]) {
            if(dst[it.first] > it.second - cur.first) {
                dst[it.first] = it.second - cur.first;
                pq.push({-dst[it.first], it.first});
            }
        }
    }

    for(i = 1; i <= n; i++) {
        cout << dst[i] << "\n";
    }

    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10