oj.uz

Submission #376636

# Submission time Handle Problem Language Result Execution time Memory
376636 2021-03-11T21:41:33 Z jeroenodb Robot (JOI21_ho_t4) C++14
0 / 100
 585 ms 38244 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 = 1e5+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);
        adj[b][c].emplace_back(d,a);
    }
    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';
    
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:38:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for(auto& [color,v]: adj[c.at]) {
      |                   ^
Main.cpp:43:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |                 auto [cost,to] = v[i];
      |                      ^
Main.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |             auto [cost,to] = v.back();
      |                  ^

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Incorrect 6 ms 5356 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 13668 KB Output is correct
2 Correct 60 ms 10092 KB Output is correct
3 Correct 214 ms 15084 KB Output is correct
4 Correct 97 ms 12012 KB Output is correct
5 Incorrect 585 ms 38244 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 3 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 5 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 5 ms 5248 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Incorrect 6 ms 5356 KB Output isn't correct
10 Halted 0 ms 0 KB -