Submission #376634

#	Time	Username	Problem	Language	Result	Execution time	Memory
376634		jeroenodb	Robot (JOI21_ho_t4)	C++17	0 / 100	1 ms	492 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e1+1;
const ll oo = 1e18;
map<int,vector<pi>> adj[mxN];
int main() {
    int n,m; cin >> n >> m;
    for(int i=0;i<m;++i) {
        int a,b,c,d; cin >> a >> b >> c >> d;
        a--,b--;
        adj[a][c].emplace_back(d,b);
    }
    vector<ll> dist(n,oo);
    dist[0] = 0;
    struct state {
        ll d;
        int at;
        bool operator<(const state& s) const {
            return d > s.d;
        }
    };
    priority_queue<state> pq;
    pq.push({0,0});
    while(!pq.empty()) {
        auto c = pq.top();
        pq.pop();
        if(c.d > dist[c.at])
            continue;
        for(auto& [color,v]: adj[c.at]) {
            sort(all(v));
            int k = v.size();
            ll total = 0;
            for(int i=0;i<k-1;++i) {
                auto [cost,to] = v[i];
                total+=cost;
                ll tmp = cost+c.d;
                if(tmp<dist[to]) {
                    pq.push({tmp,to});
                    dist[to] = tmp;
                }
            }
            auto [cost,to] = v.back();
            cost = min((ll)cost,total);
            ll tmp = cost+c.d;
            if(tmp<dist[to]) {
                pq.push({tmp,to});
                dist[to] = tmp;
            }
        }
    }
    if(dist[n-1]==oo) {
        cout  << "-1\n";
    } else cout << dist[n-1] << '\n';
    
}

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