Submission #1137747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137747		varun312	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1096 ms	3396 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
#define inf ((ll)2e17)

struct edge {
    ll a,b,c,d;
};

using pii = pair<ll, ll>;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(0);

    ll n,m;
    cin >> n >> m;

    vector<edge> v(m+1);
    // vector<vector<pii>> g(n+1);
    vector<set<pii>> g(n+1);
    for (ll i = 1; i <= m; i++) {
        cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
        // g[v[i].a].pb({v[i].b, v[i].c});
        g[v[i].a].insert({v[i].b, v[i].c});
    }

    ll ans = inf;
    for (ll i = 0; i <= m; i++) {
        // for (ll j = 0; j < g[v[i].a].size(); j++) {
        //     if (g[v[i].a][j].fi == v[i].b && g[v[i].a][j].se == v[i].c) {
        //         g[v[i].a].erase(g[v[i].a].begin() + j);
        //         g[v[i].b].pb({v[i].a, v[i].c});
        //         break;
        //     }
        // }

        g[v[i].a].erase({v[i].b, v[i].c});
        g[v[i].b].insert({v[i].a, v[i].c});
        
        vector<ll> dist(n+1, inf);
        dist[0] = dist[1] = 0;
        priority_queue<pii, vector<pii>, less<pii>> pq;
        pq.push({0, 1});
        while (!pq.empty()) {
            auto e = pq.top();
            pq.pop();
            if (dist[e.se] != e.fi) {
                continue;
            }

            for (auto nod : g[e.se]) {
                if (dist[nod.fi] > e.fi + nod.se) {
                    dist[nod.fi] = e.fi + nod.se;
                    pq.push({dist[nod.fi], nod.fi});
                }
            }
        }

        ll tmp = dist[n];
        // for (auto e : dist) {
        //     cout << e << " ";
        // }
        // cout << endl;
        
        dist.assign(n+1, inf);
        dist[0] = dist[n] = 0;
        pq.push({0, n});
        while (!pq.empty()) {
            auto e = pq.top();
            pq.pop();
            if (dist[e.se] != e.fi) {
                continue;
            }

            for (auto nod : g[e.se]) {
                if (dist[nod.fi] > e.fi + nod.se) {
                    dist[nod.fi] = e.fi + nod.se;
                    pq.push({dist[nod.fi], nod.fi});
                }
            }
        }

        // for (auto e : dist) {
        //     cout << e << " ";
        // }
        // cout << endl << endl;

        // for (ll j = 0; j < g[v[i].b].size(); j++) {
        //     if (g[v[i].b][j].fi == v[i].a && g[v[i].b][j].se == v[i].c) {
        //         g[v[i].b].erase(g[v[i].b].begin() + j);
        //         g[v[i].a].pb({v[i].b, v[i].c});
        //         break;
        //     }
        // }
        
        g[v[i].b].erase({v[i].a, v[i].c});
        g[v[i].a].insert({v[i].b, v[i].c});

        ans = min(ans, tmp + dist[1] + v[i].d);
    }

    cout << (ans == inf ? -1 : ans) << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63