제출 #1174372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174372		Hamed_Ghaffari	Robot (JOI21_ho_t4)	C++20	100 / 100	533 ms	216904 KiB

Main

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

using ll = long long;
using pll = pair<ll, ll>;
#define all(x) x.begin(), x.end()
#define pb push_back

const int MXN = 5e5+5;

int n, m, N, xr[MXN], C[MXN], P[MXN];
vector<int> g[MXN];
vector<pll> G[MXN];
ll dis[MXN];

unordered_map<int, int> V[MXN], cnt[MXN];
unordered_map<int, ll> sum[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0,u,v; i<m; i++) {
        cin >> u >> v >> C[i] >> P[i];
        xr[i] = u^v;
        g[u].pb(i);
        g[v].pb(i);
    }
    N = n+1;
    for(int v=1; v<=n; v++)
        for(int i : g[v]) {
            if(!V[v][C[i]])
                V[v][C[i]]=N++;
            cnt[v][C[i]]++;
            sum[v][C[i]] += P[i];
        }
    for(int v=1; v<=n; v++) {
        for(auto [c, u] : V[v])
            G[v].pb(pll(u, 0));
        for(int i : g[v]) {
            G[v].pb(pll(v^xr[i], cnt[v][C[i]]==1?0:P[i]));
            G[v].pb(pll(V[v^xr[i]][C[i]], 0));
            G[V[v][C[i]]].pb(pll(v^xr[i], sum[v][C[i]]-P[i]));
        }
    }
    priority_queue<pll> pq;
    pq.push({0, 1});
    fill(dis+2, dis+N, 1e18);
    while(!pq.empty()) {
        ll d = -pq.top().first;
        int v = pq.top().second;
        pq.pop();
        if(dis[v]!=d) continue;
        for(auto [u, w] : G[v])
            if(dis[u]>d+w)
                pq.push(pll(-(dis[u]=d+w), u));
    }
    cout << (dis[n]==1e18 ? -1 : dis[n]) << '\n';
    return 0;
}

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