Submission #937897

#	Time	Username	Problem	Language	Result	Execution time	Memory
937897		zwezdinv	Robot (JOI21_ho_t4)	C++17	0 / 100	366 ms	40060 KiB

Main

#include <bits/stdc++.h>

struct edge {
        int to, col;
        long long cost = 0;
        edge() = default;
        edge(int to, int col, long long cost) : to(to), col(col), cost(cost) {}
};

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, m;
        std::cin >> n >> m;
        std::vector<std::vector<edge>> g(n);
        std::vector<std::map<int, long long>> mp(n);
        for (int i = 0; i < m; ++i) {
                int u, v, c;
                long long p;
                std::cin >> u >> v >> c >> p;
                --u, --v;
                mp[u][c] += p;
                mp[v][c] += p;
                g[u].emplace_back(v, c, p);
                g[v].emplace_back(u, c, p);
        }
        std::vector<long long> dist(n, 1e18);
        dist[0] = 0;
        std::set<std::pair<long long, int>> st;
        st.emplace(0, 0);
        while (st.size()) {
                int u = st.begin()->second;
                st.erase(st.begin());
                for (auto [to, col, cost] : g[u]) {
                        long long w = std::min(cost, mp[u][col] - cost);
                        if (dist[to] > dist[u] + w) {
                                st.erase({dist[to], to});
                                dist[to] = dist[u] + w;
                                st.emplace(dist[to], to);
                        }
                }
        }
        if (dist[n - 1] == 1e18) std::cout << -1;
        else std::cout << dist[n - 1];
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42