제출 #1292389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292389		lisoth	Robot (JOI21_ho_t4)	C++20	0 / 100	215 ms	40916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

uint64_t key64(int u, int c){
    return ( (uint64_t)u << 32 ) ^ (uint64_t)c;
}

struct EdgeIn { int v; int color; ll p; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if defined(LOCAL)
    freopen("robot1.inp","r",stdin);
    freopen("robot1.out","w",stdout);
#endif

    int n;
    int m;
    if(!(cin >> n >> m)) return 0;

    vector<vector<EdgeIn>> adj(n+1);
    // we'll store total_p_per_node_color
    unordered_map<uint64_t, ll> total;
    total.reserve(m*2*2 + 10);
    total.max_load_factor(0.7f);

    vector<tuple<int,int,ll>> edges;
    edges.reserve(m);

    for(int i=0;i<m;i++){
        int a,b,c; ll p;
        cin >> a >> b >> c >> p;
        // undirected edge stored both sides
        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
        // accumulate total p for (node,color)
        total[key64(a,c)] += p;
        total[key64(b,c)] += p;
        edges.emplace_back(a,b,p);
    }

    // build graph with computed costs
    vector<vector<pair<int,ll>>> g(n+1);
    for(int u=1; u<=n; ++u){
        for(auto &e: adj[u]){
            int v = e.v;
            int color = e.color;
            ll p = e.p;
            ll tot = total[key64(u,color)]; // sum of p for color at node u
            // safety: tot >= p must hold
            ll cost = min(p, tot - p);
            g[u].push_back({v, cost});
        }
    }

    // Dijkstra
    vector<ll> dist(n+1, INF);
    dist[1] = 0;
    using pli = pair<ll,int>;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0,1});

    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if(d != dist[u]) continue;
        for(auto &ed : g[u]){
            int v = ed.first;
            ll w = ed.second;
            if(d > INF - w) continue; // overflow guard
            ll nd = d + w;
            if(nd < dist[v]){
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }

    if(dist[n] >= INF) cout << -1 << '\n';
    else cout << dist[n] << '\n';
    return 0;
}

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