Submission #1000842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000842		underwaterkillerwhale	사이버랜드 (APIO23_cyberland)	C++17	0 / 100	3030 ms	9308 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e13;
const int BASE = 137;

struct toEdge {
    int v;
    ll w;
};

int n, m, K, H;
int a[N];
vector<toEdge> ke[N];
ll dp[2][N];
bool canGo[N];

void BFS () {
    queue<int> Q;
    Q.push(1);
    canGo[1] = 1;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        iter (&id, ke[u]) {
            if (canGo[id.v] == 0) {
                canGo[id.v] = 1;
                if (id.v != H)
                    Q.push(id.v);
            }
        }
    }
}
double algo () {
    BFS();
    if (canGo[H] == 0) {
        return -1;
    }
    struct Data {
        ll u, val;
    };
    struct cmp {
        bool operator () (Data A, Data B) { return A.val > B.val; }
    };
    memset (dp, 0x3f, sizeof dp);
    auto Dijkstra = [] (ll dp[], int typ) {
        priority_queue<Data, vector<Data>, cmp> pq;
        if (typ == 0) {
            rep (i, 1, n) dp[i] = INF;
            rep (i, 1, n) if ((i == 1) || (a[i] == 0 && canGo[i])) {
                dp[i] = 0;
                pq.push({i, 0});
            }
        }
        else {
            pq.push({H, 0});
            dp[H] = 0;
        }
        while (!pq.empty()) {
            int u = pq.top().u;
            pq.pop();
            iter (&id, ke[u]) {
                int v = id.v;
                ll w = id.w;
                if (dp[v] > dp[u] + w) {
                    dp[v] = dp[u] + w;
                    pq.push({v, dp[v]});
                }
            }
        }
    };
    Dijkstra (dp[0], 0);
    Dijkstra (dp[1], 1);
    double res = INF;
    rep (i ,1, n)  {
        ll mn = INF;
        iter (&id, ke[i])  {
            if (id.v != H && a[id.v] == 2) {
                mn = min(mn, id.w);
            }
        }
        if (mn == INF) {
            res = min(res, (double)(dp[0][i] + dp[1][i]));
            continue;
        }
        double delta = dp[0][i];
        if (a[i] == 2) delta /= 2;
        rep (k, 1 + (a[i] == 2), K) {
            delta += mn;
            delta /= 2;
        }
//        cout << i <<"\n";
        res = min(res, delta + dp[1][i]);
    }
    return res;
}

double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
//void solution() {
//    cin >> n >> m >> K >> H;
//    ++H;
//    rep (i, 1, n) cin >> a[i];
//    rep (i, 1, m) {
//        int u, v, w;
//        cin >> u >> v>> w;
//        ++u, ++v;
//        ke[u].push_back({v, w});
//        ke[v].push_back({u, w});
//    }
//    cout << algo () <<"\n";
    n = _n;
    m = _m;
    K = _K;
    H = _H;
    ++H;
    rep (i, 1, n) {
        a[i] = _A[i - 1];
    }
    rep (i, 0, m - 1) {
        int u = _U[i], v = _V[i], w = _W[i];
        ++u, ++v;
        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }
    return algo();
}

//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
//    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4




3 2
0 1 5
0 2 5
1
1 2

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3