Submission #784575

#	Time	Username	Problem	Language	Result	Execution time	Memory
784575		borisAngelov	Robot (JOI21_ho_t4)	C++17	100 / 100	811 ms	84376 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = 1e18;

int n, m;

struct edge
{
    int to;
    int col;
    long long price;
};

map<int, vector<edge>> g[maxn];

long long dist[maxn];

map<int, long long> dp[maxn];
map<int, long long> sum[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, col, p;
        cin >> x >> y >> col >> p;

        g[x][col].push_back({y, col, p});
        g[y][col].push_back({x, col, p});

        sum[x][col] += p;
        sum[y][col] += p;
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, pair<int, int>>> pq;
    pq.push(make_pair(0LL, make_pair(1, 0)));
    dist[1] = 0;

    while (!pq.empty())
    {
        long long curr = -pq.top().first;
        int node = pq.top().second.first;
        int col = pq.top().second.second;

        pq.pop();

        if (col != 0 && dp[node][col] == curr)
        {
            for (auto e : g[node][col])
            {
                long long path = curr + sum[node][col] - e.price;

                if (dist[e.to] > path)
                {
                    dist[e.to] = path;
                    pq.push(make_pair(-path, make_pair(e.to, 0)));
                }
            }
        }
        else if (col == 0 && dist[node] == curr)
        {
            for (auto edges : g[node])
            {
                for (auto e : edges.second)
                {
                    long long path1 = curr + sum[node][e.col] - e.price;

                    if (dist[e.to] > path1)
                    {
                        dist[e.to] = path1;
                        pq.push(make_pair(-path1, make_pair(e.to, 0)));
                    }

                    long long path2 = curr + e.price;

                    if (dist[e.to] > path2)
                    {
                        dist[e.to] = path2;
                        pq.push(make_pair(-path2, make_pair(e.to, 0)));
                    }

                    long long path3 = curr;

                    if (dp[e.to].find(e.col) == dp[e.to].end() || path3 < dp[e.to][e.col])
                    {
                        dp[e.to][e.col] = path3;
                        pq.push(make_pair(-path3, make_pair(e.to, e.col)));
                    }
                }
            }
        }
    }

    if (dist[n] == inf)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[n] << endl;
    }

    return 0;
}

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