Submission #1185899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185899		vincentbucourt1	Robot (JOI21_ho_t4)	C++20	0 / 100	3097 ms	46132 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
// #define int long long
#define ll long long
#define f first
#define s second

const ll INF = (int)1e18;
const int MAXV = 100'020;
const int MAXE = 200'020;

int V, E;
struct Edge {
    int nodes[2];
    int color;
    ll price;
};
Edge edges[MAXE];
vector<int> adj[MAXV];
map<int,ll> sumColor[MAXV];
struct Situ {
    ll len;
    int iEdge;
    bool side, changeC;
    bool operator< (const Situ& other) const {
        return len < other.len;
    }
    bool operator> (const Situ& other) const {
        return len > other.len;
    }
};
ll SP[MAXE][2][2];

signed main() {
    fastIO();
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                SP[i][j][k] = INF;
            }
        }
    }
    for (int i = 0; i < E; i++) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        u--, v--;
        edges[i] = {{u, v}, c, p};
        adj[u].push_back(i);
        adj[v].push_back(i);
        if (sumColor[u].find(c) == sumColor[u].end()) sumColor[u][c] = 0ll;
        sumColor[u][c] += p;
        if (sumColor[v].find(c) == sumColor[v].end()) sumColor[v][c] = 0ll;
        sumColor[v][c] += p;
    }
    priority_queue<Situ, vector<Situ>, greater<Situ>> PQ;
    for (int iEdge : adj[0]) {
        Edge edgeOn = edges[iEdge];
        if (edgeOn.nodes[0] != 0) {
            SP[iEdge][0][0] = sumColor[0][edgeOn.color] - edgeOn.price;
            PQ.push({SP[iEdge][0][0], iEdge, 0, 0});
            SP[iEdge][0][1] = edgeOn.price;
            PQ.push({SP[iEdge][0][1], iEdge, 0, 1});
        }
        else {
            SP[iEdge][1][0] = sumColor[0][edgeOn.color] - edgeOn.price;
            PQ.push({SP[iEdge][1][0], iEdge, 1, 0});
            SP[iEdge][1][1] = edgeOn.price;
            PQ.push({SP[iEdge][1][1], iEdge, 1, 1});
        }
    }
    while (!PQ.empty()) {
        Situ on = PQ.top();
        PQ.pop();
        if (on.len > SP[on.iEdge][on.side][on.changeC]) continue;
        Edge edgeOn = edges[on.iEdge];
        int nodeOn = edges[on.iEdge].nodes[on.side];
        for (int iEdgeNxt : adj[nodeOn]) {
            if (iEdgeNxt == on.iEdge) continue;
            Edge edgeNxt = edges[iEdgeNxt];
            bool iNodeNxt = (edgeNxt.nodes[0] != nodeOn ? 0 : 1);
            ll cost = edgeNxt.price + on.len;
            if (cost < SP[iEdgeNxt][iNodeNxt][1]) {
                SP[iEdgeNxt][iNodeNxt][1] = cost;
                PQ.push({SP[iEdgeNxt][iNodeNxt][1], iEdgeNxt, iNodeNxt, 1});
            }
            cost = sumColor[nodeOn][edgeNxt.color] - edgeNxt.price - (edgeOn.color == edgeNxt.color && on.changeC ? edgeOn.price : 0) + on.len;
            if (cost < SP[iEdgeNxt][iNodeNxt][0]) {
                SP[iEdgeNxt][iNodeNxt][0] = cost;
                PQ.push({SP[iEdgeNxt][iNodeNxt][0], iEdgeNxt, iNodeNxt, 0});
            }
        }
    }
    ll ans = INF;
    for (int iEdge = 0; iEdge < E; iEdge++) {
        Edge edgeOn = edges[iEdge];
        for (int j = 0; j < 2; j++) {
            if (edgeOn.nodes[j] == V-1) {
                ans = min({ans, SP[iEdge][j][0], SP[iEdge][j][1]});
            }
        }
    }
    cout << (ans != INF ? ans : -1) << "\n";
}

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