제출 #1181538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181538		finalpoi	Robot (JOI21_ho_t4)	C++20	34 / 100	3099 ms	101996 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pr=pair<ll,int>; // odl, wie
using tpl=tuple<int,ll,int>; // kolor, odl, wie
#define nl '\n'
#define pb push_back
#define sz(x) (int)(x).size()
#define each(a, b) for(const auto& a:b)
#define rep(a, b) for(int a=0; a<(b); a++)
#define coz(x) cerr<<(#x)<<": "<<(x)<<'\n'
#define cot(x, l, n) cerr<<(#x)<<": "; \
for(int i=l; i<l+n; i++) { cerr<<x[i]<<' '; } cerr<<'\n'

inline int ri() {
    int x=0;
    char ch=getchar_unlocked();
    while (ch<'0' || ch>'9') {
        ch=getchar_unlocked();
    }
    while (ch>='0' && ch<='9') {
        x=x*10+(ch-'0');
        ch=getchar_unlocked();
    }
    return x;
}

constexpr int N=1e5+6;
constexpr ll INF=1e17;

auto cmp=[](const tpl& a, const tpl& b) {
    return get<1>(a)>get<1>(b);
};

priority_queue<tpl, vector<tpl>, decltype(cmp)> pq(cmp);
vector<tpl> adj[N];
unordered_map<int,vector<pr>> col[N];
// ll odl[N];
unordered_map<int,ll> sum[N];
unordered_map<int,ll> odl[N];
int n,m;

ll get_odl(int w, int c) {  
    auto iter=odl[w].find(c);
    if(iter==odl[w].end()) return INF;
    return iter->second;
}

void dij(int w) {
    pq.push({0,0,w});
    odl[w][0]=0;
    while(!pq.empty()) {
        ll ad; int k,a;
        tie(k,ad,a)=pq.top();
        pq.pop();
        if(ad!=get_odl(a,k)) continue;
        each(e, adj[a]) {
            ll p; int c,b;
            tie(c,p,b)=e;
            if(k==0) {
                // c
                ll alt=ad;
                if(alt<get_odl(b,c)) {
                    odl[b][c]=alt;
                    pq.push({c,odl[b][c],b});
                }
                // 0
                ll cur=min(sum[a][c]-p, p)+ad;
                if(cur<get_odl(b,0)) {
                    odl[b][0]=cur;
                    pq.push({0,odl[b][0],b});
                }
            }
        }
        if(k==0) continue;
        auto iter=col[a].find(k);
        if(iter==col[a].end()) continue;
        each(e, col[a][k]) { // k!=0
            // 0
            ll p; int b;
            tie(p,b)=e;
            ll cur=sum[a][k]-p+ad;
            if(cur<get_odl(b,0)) {
                odl[b][0]=cur;
                pq.push({0,odl[b][0],b});
            }
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    // cin>>n>>m;
    n=ri(); m=ri();
    rep(_, m) {
        int a,b,c,p;
        // cin>>a>>b>>c>>p;
        a=ri(); b=ri(); c=ri(); p=ri();
        adj[a].pb({c,p,b});
        adj[b].pb({c,p,a});
        col[a][c].pb({p,b});
        col[b][c].pb({p,a});
        sum[a][c]+=p;
        sum[b][c]+=p;
    }
    dij(1);
    ll ans=get_odl(n,0);
    if(ans==INF) {
        cout<<"-1\n";
    } else {
        cout<<ans<<nl;
    }
}

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