제출 #670523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670523		finn__	Robot (JOI21_ho_t4)	C++17	0 / 100	132 ms	13732 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()
{
    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, unsigned>> 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]++;
            else
                colors[u][c] = 1;
        }
    }

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

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

        auto it = dis[u].find(c0);
        if (it == dis[u].end() || it->second != z)
            continue;

        for (auto const &[v, c, p] : g[u])
        {
            unsigned cc = colors[u][c];

            if (cc > 1)
            {
                if (c == c0 && cc == 2 && (dis[v].find(c) == dis[v].end() || z < dis[v][c]))
                {
                    dis[v][c] = z;
                    q.push({v, c, z});
                }

                if (dis[v].find(m + 1) == dis[v].end() || z + p < dis[v][m + 1])
                {
                    dis[v][m + 1] = z + p;
                    q.push({v, m + 1, z + p});
                }
            }
            else if (dis[v].find(c) == dis[v].end() || z < dis[v][c])
            {
                dis[v][c] = z;
                q.push({v, c, z});
            }
        }
    }

    int64_t min_dis = INT64_MAX;

    for (auto const [c, d] : dis[n - 1])
        min_dis = min(min_dis, d);

    if (min_dis == INT64_MAX)
        cout << -1 << '\n';
    else
        cout << min_dis << '\n';
}

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