Submission #1181531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181531		finalpoi	Robot (JOI21_ho_t4)	C++20	34 / 100	3098 ms	61444 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
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];
// 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) {
    // for(int i=1; i<=n; i++) {
    //     odl[i]=INF;
    // }
    pq.push({0,0,w});
    // odl[w]=0;
    odl[w][0]=0;
    while(!pq.empty()) {
        ll ad; int k,a;
        tie(k,ad,a)=pq.top();
        pq.pop();
        // if(ad!=odl[a]) continue;
        if(ad!=get_odl(a,k)) continue;
        each(e, adj[a]) {
            ll p; int c,b;
            tie(c,p,b)=e;
            if(k==0) { // czy gdzies nie zamienilem (k,c)?
                // 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});
                }
            } else if(k==c) { // k!=0
                // 0
                ll cur=sum[a][c]-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});
        sum[a][c]+=p;
        sum[b][c]+=p;
    }
    // for(int i=1; i<=n; i++) {
    //     cerr<<i<<'\n';
    //     each(cp, sum[i]) {
    //         cerr<<cp.first<<' '<<cp.second<<nl;
    //     }
    // }
    // cerr<<"===\n";
    dij(1);
    ll ans=get_odl(n,0);
    // each(kv, odl[n]) {
    //     cerr<<kv.second<<' ';
    //     ans=min(ans,kv.second);
    // }
    // cerr<<nl;
    if(ans==INF) {
        cout<<"-1\n";
    } else {
        cout<<ans<<nl;
    }
    // cot(odl,1,n);
}

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