Submission #1292387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292387		dungnt	Robot (JOI21_ho_t4)	C++20	100 / 100	127 ms	15496 KiB

Main

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

struct E
{
    int v, c, w;
    E(){}
    E(int _v, int _c, int _w)
    {
        v = _v;
        c = _c;
        w = _w;
    }
};

const int N = 100000 + 5;
const int M = 200000 + 5;
const long long INF = 1e18;

vector<E> g[N];
long long d[N];
long long sum[M];
long long best[M];

int n, m;

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

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int u, v, c, w;
        cin >> u >> v >> c >> w;
        g[u].push_back(E(v, c, w));
        g[v].push_back(E(u, c, w));
    }

    for (int i = 1; i <= n; i++)
        d[i] = INF;

    for (int i = 1; i <= m; i++)
        best[i] = INF;

    d[1] = 0;

    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<pair<long long,int>>
    > pq;

    pq.push({0, 1});

    while (!pq.empty())
    {
        long long du = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (du != d[u])
            continue;

        for (auto &e : g[u])
        {
            sum[e.c] += e.w;
            if (best[e.c] > d[e.v])
                best[e.c] = d[e.v];
        }

        for (auto &e : g[u])
        {
            int v = e.v;
            int c = e.c;
            int w = e.w;

            long long t1 = w < sum[c] - w ? w : sum[c] - w;
            long long nd1 = du + t1;

            if (d[v] > nd1)
            {
                d[v] = nd1;
                pq.push({nd1, v});
            }

            long long nd2 = best[c] + sum[c] - w;

            if (d[v] > nd2)
            {
                d[v] = nd2;
                pq.push({nd2, v});
            }
        }

        for (auto &e : g[u])
        {
            sum[e.c] = 0;
            best[e.c] = INF;
        }
    }

    if (d[n] == INF)
        cout << -1;
    else
        cout << d[n];
}

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