Submission #476797

#	Time	Username	Problem	Language	Result	Execution time	Memory
476797		Rainbowbunny	Robot (JOI21_ho_t4)	C++17	100 / 100	1450 ms	118220 KiB

Main

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

const int MAXN = 2e5 + 5;
const long long INF = 1e18;

struct ToEdge
{
    int v, c;
    long long p;
    ToEdge(int v = 0, int c = 0, long long p = 0) : v(v), c(c), p(p) {}
};

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

int n, m;
long long p[MAXN];
vector <ToEdge> E[MAXN];
map <int, long long> Sum[MAXN];
map <int, vector <ToEdge> > Adj[MAXN];
map <int, long long> Dist[MAXN];

void Add(long long dist, int node, int color)
{
    if(Dist[node][color] > dist)
    {
        Dist[node][color] = dist;
        pq.push(make_tuple(dist, node, color));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v, c;
        long long p;
        cin >> u >> v >> c >> p;
        E[u].emplace_back(v, c, p);
        E[v].emplace_back(u, c, p);
        Adj[u][c].emplace_back(v, c, p);
        Adj[v][c].emplace_back(u, c, p);
        Dist[u][c] = INF;
        Dist[v][c] = INF;
        Sum[u][c] += p;
        Sum[v][c] += p;
    }
    for(int i = 1; i <= n; i++)
    {
        Dist[i][0] = INF;
    }
    Add(0, 1, 0);
    while(pq.empty() == false)
    {
        int node, color;
        long long dist;
        tie(dist, node, color) = pq.top();
        pq.pop();
        if(dist == Dist[node][color])
        {
            if(color == 0)
            {
                for(auto x : E[node])
                {
                    Add(dist, x.v, x.c);
                    Add(dist + min(Sum[node][x.c] - x.p, x.p), x.v, 0);
                    assert(Sum[node][x.c] - x.p >= 0);
                }
            }
            else
            {
                for(auto x : Adj[node][color])
                {
                    Add(dist + Sum[node][color] - x.p, x.v, 0);
                    assert(Sum[node][color] - x.p >= 0);
                }
            }
        }
    }
    if(Dist[n][0] == INF)
    {
        Dist[n][0] = -1;
    }
    cout << Dist[n][0] << '\n';
}

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