oj.uz

Submission #376634

# Submission time Handle Problem Language Result Execution time Memory
376634 2021-03-11T21:39:40 Z jeroenodb Robot (JOI21_ho_t4) C++17
0 / 100
 1 ms 492 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -