Submission #1200162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200162		vux2code	Robot (JOI21_ho_t4)	C++20	0 / 100	3098 ms	169304 KiB

Main

// Src : Vux2Code
/* Note :
    
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define fi first
#define se second

#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}

// debug (+20)
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template<typename... Args>
void debug_impl(const char* names, Args&&... args) {
    vector<string> _names;
    {
        istringstream ss(names);
        string token;
        while (getline(ss, token, ',')) {
            auto l = token.find_first_not_of(" \t");
            auto r = token.find_last_not_of(" \t");
            if (l == string::npos) _names.push_back("");
            else _names.push_back(token.substr(l, r - l + 1));
        }
    }
    cerr << "(";
    size_t _i = 0;
    int _dummy[] = { 0, ((cerr << _names[_i] << " : " << args << (++_i < _names.size() ? ", " : "")), 0)... };
    (void)_dummy;
    cerr << ")" << endl;
}

// Triple (+12)
struct tri {
    ll fi, se, th;
    tri(ll _fi, ll _se, ll _th) : fi(_fi), se(_se), th(_th) {}
    bool operator<(const tri& o) const {
        if (fi != o.fi) return fi < o.fi;
        if (se != o.se) return se < o.se;
        return th < o.th;
    }
    bool operator>(const tri& o) const {
        return o < *this;
    }
};

template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))

#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())

const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }

/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;

/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }

ll t = 1;

ll n, m;
vector <tri> adj [maxN];
rvs_pq <tri> q;
map <ll, ll> dis [maxN], sum [maxN];

void ck (ll x, ll y, ll val) {
    if (dis [x]. find (y) == dis [x]. end () || dis [x] [y] > val) {
        dis [x] [y] = val;
        q. push ({val, x, y});
    }
}

void solve() {
    cin >> n >> m;
    forinc (i, 1, m) {
        ll a, b, c, p;
        cin >> a >> b >> c >> p;
        adj [a]. pusb ({b, c, p});
        adj [b]. pusb ({a, c, p});
        sum [a] [c] += p;
        sum [b] [c] += p;
    }
    dis [1] [0] = 0;
    q. push ({dis [1] [0], 1, 0});
    while (!q. empty ()) {
        ll d  = q. top (). fi;
        ll id = q. top (). se;
        ll c  = q. top (). th;
        q. pop ();
        if (dis [id] [c] != d) continue;
        // cerr << id << ' ' << c << ' ' << d << '\n'; 
        for (tri i : adj [id]) {
            if (i. se != c) ck (i. fi, i. se, dis [id] [c] + sum [id] [i. se] - i. th);
            ck (i. fi, 0, dis [id] [c] + i. th);
        } 
    }
    // forinc (i, 1, n) {
    //     cerr << i << '\n';
    //     for (pll j : dis [i]) {
    //         cerr << j. fi << ' ' << j. se << '\n';
    //     }
    // }
    ll ans = inf64;
    for (pll i : dis [n]) mini (ans, i. se);
    cout << (ans == inf64 ? -1 : ans);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    // cin >> t;
    while (t--) solve();
}

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