Submission #1194098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194098		zh_h	Cyberland (APIO23_cyberland)	C++17	0 / 100	16 ms	6980 KiB

cyberland

#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> abi) {
    if (n == 2) {
        return c[0];
    }

    vector<vector<pair<int, double>>> edge(n);
    for (int i = 0; i < m; i ++) {
        edge[x[i]].pb({y[i], c[i]});
        edge[y[i]].pb({x[i], c[i]});
    }

    double ans = -1;
    vector<int> visited(n, 0);
    vector<double> dis(n, 1e9);
    priority_queue<tuple<double, int, int>> pq;
    pq.push(make_tuple(0, 0, 0)); // -w, v, k
    visited[0] ++;
    dis[0] = 0;
    while (!pq.empty()) {
        tuple<double, int, int> cur = pq.top(); pq.pop();
        double w = get<0>(cur); w *= -1;
        int v = get<1>(cur), k = get<2>(cur);

        if (visited[v] == 2) {continue;}
        visited[v] ++;

        if (abi[v] == 0) {dis[v] = 0;}

        for (auto [cv, cw] : edge[v]) {
            if (dis[cv] > dis[v] + cw) {
                dis[cv] = dis[v] + cw;
                pq.push({make_tuple(-cw, cv, k)});
            }
        }
    }

    if (dis[h] == 1e9) return -1;
    else return dis[h];
}

• 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