Submission #937921

#	Time	Username	Problem	Language	Result	Execution time	Memory
937921		zwezdinv	Robot (JOI21_ho_t4)	C++17	100 / 100	1197 ms	94332 KiB

Main

#include <bits/stdc++.h>


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

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

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