제출 #670552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670552		finn__	Robot (JOI21_ho_t4)	C++17	34 / 100	3071 ms	45152 KiB

Main

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

struct edge
{
    unsigned v, c;
    int64_t p;
};

struct state
{
    unsigned u, c;
    int64_t z;

    bool operator<(state const &s) const
    {
        return z > s.z;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    unsigned n, m;
    cin >> n >> m;

    vector<vector<edge>> g(n);
    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v, c;
        int64_t p;
        cin >> u >> v >> c >> p;
        g[u - 1].push_back({v - 1, c, p});
        g[v - 1].push_back({u - 1, c, p});
    }

    vector<map<unsigned, int64_t>> colors(n);

    for (unsigned u = 0; u < n; u++)
    {
        for (auto const &[v, c, p] : g[u])
        {
            if (colors[u].find(c) != colors[u].end())
                colors[u][c] += p;
            else
                colors[u][c] = p;
        }
    }

    priority_queue<state> q;
    q.push((state){0, m + 1, 0});
    vector<int64_t> dp1(n, INT64_MAX);
    vector<map<unsigned, int64_t>> dp2(n);
    dp1[0] = 0;

    while (!q.empty())
    {
        dp2[0][m + 1] = 0;

        auto const [u, c0, z] = q.top();
        q.pop();

        if (c0 < m + 1)
        {
            // Consider the case that a edge was just flipped, and for the next
            // edge, all other edges except the flipped one must be flipped.
            if (dp2[u][c0] != z)
                continue;

            for (auto const &[v, c, p] : g[u])
            {
                if (c == c0 && z + colors[u][c] - p < dp1[v])
                {
                    dp1[v] = z + colors[u][c] - p;
                    q.push({v, m + 1, dp1[v]});
                }
            }
        }
        else
        {
            if (dp1[u] != z)
                continue;

            for (auto const &[v, c, p] : g[u])
            {
                if (z + colors[u][c] - p < dp1[v])
                {
                    dp1[v] = z + colors[u][c] - p;
                    q.push({v, m + 1, dp1[v]});
                }

                if (z + p < dp1[v])
                {
                    dp1[v] = z + p;
                    q.push({v, m + 1, z + p});
                }

                if (dp2[v].find(c) == dp2[v].end() || z < dp2[v][c])
                {
                    dp2[v][c] = z;
                    q.push({v, c, z});
                }
            }
        }
    }

    if (dp1[n - 1] == INT64_MAX)
        cout << -1 << '\n';
    else
        cout << dp1[n - 1] << '\n';
}

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