제출 #1126221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126221		LucaIlie	Robot (JOI21_ho_t4)	C++20	100 / 100	575 ms	93940 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c, p;

    int other( int w ) {
        return u ^ v ^ w;
    }
};

struct elemPQ {
    int u;
    long long d;

    bool operator < ( const elemPQ &x ) const {
        return x.d < d;
    }
};

const int MAX_N = 1e5;
const int MAX_M = 2e5;
const long long INF = 1e18;
bool vis[MAX_N + 1];
long long dist[MAX_N + 1];
edge edges[MAX_M + 1];
vector<int> adj[MAX_N + 1];
unordered_map<int, int> maxEdge[MAX_N + 1], maxEdge2[MAX_N + 1];
unordered_map<int, long long> sumColor[MAX_N + 1];
priority_queue<elemPQ> pq;

int main() {
    int n, m;

    cin >> n >> m;
    for ( int e = 1; e <= m; e++ ) {
        cin >> edges[e].u >> edges[e].v >> edges[e].c >> edges[e].p;
        adj[edges[e].u].push_back( e );
        adj[edges[e].v].push_back( e );
    }

    for ( int v = 1; v <= n; v++ ) {
        dist[v] = INF;
        for ( int e: adj[v] ) {
            int c = edges[e].c, p = edges[e].p;
            sumColor[v][c] += p;
            if ( p > edges[maxEdge[v][c]].p ) {
                maxEdge2[v][c] = maxEdge[v][c];
                maxEdge[v][c] = e;
            } else if ( p > edges[maxEdge2[v][c]].p )
                maxEdge2[v][c] = e;
        }
    }

    dist[1] = 0;
    pq.push( { 1, dist[1] } );
    while ( !pq.empty() ) {
        int u = pq.top().u;
        pq.pop();

        //printf( "%d %lld\n", u, dist[u] );
        if ( vis[u] )
            continue;
        vis[u] = true;

        for ( int e: adj[u] ) {
            int v = edges[e].other( u ), c = edges[e].c, p = edges[e].p;

            if ( dist[u] + p < dist[v] ) {
                dist[v] = dist[u] + p;
                pq.push( { v, dist[v] } );
            }

            if ( dist[u] + sumColor[u][c] - p < dist[v] ) {
                dist[v] = dist[u] + sumColor[u][c] - p;
                pq.push( { v, dist[v] } );
            }

            int f = 0;
            if ( maxEdge[v][c] == e )
                f = maxEdge2[v][c];
            else
                f = maxEdge[v][c];

            if ( f != 0 ) {
                int w = edges[f].other( v );
                if ( dist[u] + sumColor[v][c] - edges[f].p < dist[w] ) {
                    dist[w] = dist[u] + sumColor[v][c] - edges[f].p;
                    pq.push( { w, dist[w] } );
                }
            }
        }
    }

    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";

    return 0;
}

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