Submission #476778

#	Time	Username	Problem	Language	Result	Execution time	Memory
476778		Rainbowbunny	Robot (JOI21_ho_t4)	C++17	24 / 100	3086 ms	554044 KiB

Main

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

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

struct ToEdge
{
    int v;
    long long p;
    ToEdge(int v = 0, long long p = 0) : v(v), 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];
map <int, int> 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;
        Adj[u][c].emplace_back(v, p);
        Adj[v][c].emplace_back(u, 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 : Adj[node])
                {
                    for(auto y : x.second)
                    {
                        Add(dist, y.v, x.first);
                        Add(dist + min(y.p, Sum[node][x.first] - y.p), y.v, 0);
                    }
                }
            }
            else
            {
                for(auto x : Adj[node][color])
                {
                    Add(dist + Sum[node][color] - x.p, x.v, 0);
                }
            }
        }
    }
    if(Dist[n][0] == INF)
    {
        Dist[n][0] = -1;
    }
    cout << Dist[n][0] << '\n';
}

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