Submission #1188142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188142		patgra	Robot (JOI21_ho_t4)	C++20	100 / 100	687 ms	103956 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr ll inf = 1e18;
int n, m;
vector<vector<array<int, 3>>> g;
vector<unordered_map<int, ll>> dist, sumColChange;
vector<unordered_map<int, vector<int>>> indicesCol;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    g.resize(n + 1); dist.resize(n + 1), sumColChange.resize(n + 1), indicesCol.resize(n + 1);
    rep(i, 0, m) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        indicesCol[a][c].pb((int)g[a].size());
        indicesCol[b][c].pb((int)g[b].size());
        g[a].pb({b, c, d});
        g[b].pb({a, c, d});
        sumColChange[a][c] += d;
        sumColChange[b][c] += d;
    }

    ll ans = inf;
    dist[1][0] = 0;
    priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<>> Q;
    Q.push({0, {1, 0}});
    while(!Q.empty()) {
        auto [d, vc] = Q.top(); Q.pop();
        auto [v, c] = vc;
        if(dist[v][c] < d) continue;
        DC << "dist[" << v << "][" << c << "] = " << d << eol;
        if(v == n && c == 0) ans = min(ans, d);
        dist[v][c] = -1;
        if(c == 0) {
            for(auto [u, c1, c2] : g[v]) {
                ll d2 = d + sumColChange[v][c1] - c2;
                if(!dist[u].contains(0)) dist[u][0] = inf;
                if(dist[u][0] > d2) dist[u][0] = d2, Q.push({d2, {u, 0}});
                d2 = d + c2;
                if(!dist[u].contains(c1)) dist[u][c1] = inf;
                if(dist[u][c1] > d2 - c2) dist[u][c1] = d2 - c2, Q.push({d2 - c2, {u, c1}});
                if(dist[u][0] > d2) dist[u][0] = d2, Q.push({d2, {u, 0}});
            }
            continue;
        }
        repIn(ind, indicesCol[v][c]) {
            auto [u, c1, c2] = g[v][ind];
            ll d2 = d + sumColChange[v][c1] - c2;
            if(!dist[u].contains(0)) dist[u][0] = inf;
            if(dist[u][0] > d2) dist[u][0] = d2, Q.push({d2, {u, 0}});
        }
    }

    cout << (ans == inf ? -1 : ans) << '\n';
}

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