Submission #1100839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100839		NoMercy	Cyberland (APIO23_cyberland)	C++17	0 / 100	25 ms	6992 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 99;

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    vector<array<int, 2>> g[N + 1];
    for (int i = 0;i < M;i ++) {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }

    vector<int> dp(N + 1, inf);
    dp[1] = 0;
    multiset<array<int, 2>> ms;
    ms.insert({0, 1});
    while (ms.size() > 0) {
        auto it = *ms.begin();
        ms.erase(ms.begin());
        if (it[1] == H) continue;
        for (auto [v, w] : g[it[1]]) if (dp[v] > (arr[v] == 0 ? 0 : it[0] + w)) {
            dp[v] = (arr[v] == 0 ? 0 : it[0] + w);
            ms.insert({dp[v], v});
        }
    }
    return dp[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