Submission #1245969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245969		nasjes	Robot (JOI21_ho_t4)	C++20	100 / 100	1308 ms	129648 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 3*1e5+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e18+3;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
vector<pll> a[dim];
map<ll, vector<pair<pll, ll>>> g[dim];
struct edge{
    ll u, v, c, p;
};
edge ed[dim];
ll dey(ll st, vector<map<ll, ll>> &dst){
    dst[st][0]=0;
    set<pair<ll, pll>> q;
    q.insert({0, {st, 0}});
    while(q.size()>0) {
        ll v = (*q.begin()).se.fi;
        ll tp = (*q.begin()).se.se;
        if(dst[v][tp]==inf)break;
    //    cout<<v<<" "<<tp<<" "<<dst[v][tp]<<endl;
        q.erase(q.begin());
        for (auto x: g[v][tp]) {
            ll to1 = x.fi.fi;
            ll to2 = x.fi.se;
            if (dst[to1][to2] > dst[v][tp] + x.se) {
                q.erase({dst[to1][to2], {to1, to2}});
                dst[to1][to2] = dst[v][tp] + x.se;
                q.insert({dst[to1][to2], {to1, to2}});
            }
        }
    }
    return dst[n][0];

}
int main() {
    ll t, u0, v0;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        cin>>ed[i].u>>ed[i].v>>ed[i].c>>ed[i].p;
        a[ed[i].u].pb({ed[i].v, i});
        a[ed[i].v].pb({ed[i].u, i});
    }
    vector<map<ll, ll>> dst(n+5);
    for(int i=1; i<=n; i++){
        map<ll, ll> mp;
        dst[i][0]=inf;
        ll mn=inf;
        for(auto x: a[i]){
            ll id=x.se;
            ll c=ed[id].c;
            dst[i][c]=inf;
            mp[c]+=ed[id].p;
        }
        //if(i==1)cout<<
        for(auto x:a[i]){
            g[i][0].pb({{x.fi, ed[x.se].c}, 0});
            g[i][0].pb({ {x.fi, 0}, min(mp[ed[x.se].c]-ed[x.se].p, ed[x.se].p)});
            g[i][ed[x.se].c].pb({{x.fi, 0}, mp[ed[x.se].c]-ed[x.se].p});

           // g[x.fi][ed[x.se].c].pb({{x.fi, 0}, ed[x.se].p});
           // g[x.fi][0].pb({{x.fi, ed[x.se].c}, ed[x.se].p});
        }
    }
    ll ans=dey(1, dst);
    if(ans>=inf){
        cout<<-1<<endl;
    }
    else{
        cout<<ans<<endl;
    }


    return 0;
}

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