Submission #958607

#	Time	Username	Problem	Language	Result	Execution time	Memory
958607		daoda	Robot (JOI21_ho_t4)	C++17	0 / 100	73 ms	10544 KiB

Main

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(int x=a;x < int(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

// typedef tree<int,null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> Indexed_set;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double ld;

const int INF = int(1e9) + 10;
const ll INIT = 7;
const ll MAX_VAL = (ll) 1e9;
const ll MAX_SZ = (ll) 2e5;
const long double eps = 1e-4;
const int MOD = 998244353;

vi rd = {0, 1 , 0, -1}, cd = {1, 0, -1, 0};

struct Road {
    int to, c, p;
    bool only = false;
};

int main() { 

    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    fast

    // TESTCASE {

    // }    

    int n, m;
    cin >> n >> m;

    vector<vector<Road>> adj(n + 1);

    FOR(i, 0, m) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;

        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
    }

    auto cmp = [&](Road& a, Road& b) {
        if(a.c == b.c) return a.p < b.p;
        return a.c < b.c;
    };

    FOR(i, 1, n + 1) {
        sort(adj[i].begin(), adj[i].end(), cmp);

        int j = 0;

        vi same;

        while(j <= int(adj[i].size())) {
            if(j == int(adj[i].size()) || (j && adj[i][j].c != adj[i][j - 1].c)) {
                int sz = same.size();

                if(sz > 1) {
                    vi sums(sz);
                    sums[0] = adj[i][same[0]].p;

                    FOR(k, 1, sz) sums[k] = sums[k - 1] + adj[i][same[k]].p;
                    FOR(k, 0, sz - 1) {
                        if(sums[sz - 2] - adj[i][same[k]].p < adj[i][same[sz - 1]].p) {
                            adj[adj[i][k].to].push_back({adj[i][same[sz - 1]].to, INF, sums[sz - 2]});
                        }
                    }
                    
                    if(sz >= 3) adj[adj[i][same[sz - 1]].to].push_back({adj[i][same[sz - 2]].to, INF, adj[i][same[sz - 1]].p + sums[sz - 3]});

                    adj[i][same[sz - 1]].p = min(adj[i][same[sz - 1]].p, sums[sz - 2]);
                } else if(sz == 1) adj[i][same.back()].only = true;

                same.clear();
            } else if(adj[i][j].p == INF) break;

            same.push_back(j);
            j++;
        }
    }

    priority_queue<pll, vpll, greater<pll>> tr;
    vll sp(n + 1, -1);

    tr.push(make_pair(0ll, 1ll));

    while(!tr.empty()) {
        auto [dist, crossing] = tr.top();
        tr.pop();

        if(sp[crossing] != -1) continue;

        sp[crossing] = dist;

        if(crossing == n) break;

        for(auto [to, c, p, only] : adj[crossing]) {
            tr.push(make_pair(dist + (only ? 0 : p), to));
        }
    }

    cout << sp[n];
}   

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