Submission #1092384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092384		ortsac	Robot (JOI21_ho_t4)	C++17	100 / 100	1270 ms	146564 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAXN = 1e5 + 10;

struct Edge {
    int to, cor, p;
    Edge(int a = 0, int b = 0, int c = 0) : to(a), cor(b), p(c) {}
};

struct State {
    int v, cor;
    State(int a = 0, int b = 0) : v(a), cor(b) {}
    bool operator < (const State& a) const {
        return (make_pair(v, cor) < make_pair(a.v, a.cor));
    }
};

map<int, vector<Edge>> adj[MAXN];
map<int, int> psum[MAXN], dp[MAXN];
map<int, bool> vis[MAXN], prop[MAXN];

int32_t main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, p;
        cin >> a >> b >> c >> p;
        adj[a][c].push_back(Edge(b, c, p));
        adj[b][c].push_back(Edge(a, c, p));
        psum[a][c] += p;
        psum[b][c] += p;
    }
    priority_queue<pair<int, State>> pq;
    pq.push({0, State(1, 0)});
    vis[1][0] = 1;
    while (!pq.empty()) {
        auto node = pq.top().second;
        pq.pop();
        if (prop[node.v][node.cor]) continue;
        prop[node.v][node.cor] = 1;
        int d = dp[node.v][node.cor];
        //cout << node.v << " " << node.cor << " " << d << "\n";
        if (node.cor) {
            for (auto u : adj[node.v][node.cor]) {
                int cost = (psum[node.v][node.cor] - u.p);
                int case1 = (d + cost);
                if (!vis[u.to][0] || case1 < dp[u.to][0]) {
                    vis[u.to][0] = 1;
                    dp[u.to][0] = case1;
                    pq.push({-case1, State(u.to, 0)});
                    // he pays for the previous one
                }
            }
        } else {
            for (auto &i : adj[node.v]) {
                for (Edge u : i.second) {
                    // flip the rest
                    int case1 = (d + psum[node.v][u.cor] - u.p);
                    if (!vis[u.to][0] || case1 < dp[u.to][0]) {
                        vis[u.to][0] = 1;
                        dp[u.to][0] = case1;
                        pq.push({-case1, State(u.to, 0)});
                    }
                    // flip j and pay directly
                    int case2 = (d + u.p);
                    if (!vis[u.to][0] || case2 < dp[u.to][0]) {
                        vis[u.to][0] = 1;
                        dp[u.to][0] = case2;
                        pq.push({-case2, State(u.to, 0)});
                    }
                    // pay it forward!!
                    int case3 = d;
                    if (!vis[u.to][u.cor] || case3 < dp[u.to][u.cor]) {
                        vis[u.to][u.cor] = 1;
                        dp[u.to][u.cor] = case3;
                        pq.push({-case3, State(u.to, u.cor)});
                    }
                }
            }
        }
    }
    if (!vis[n][0]) {
        cout << "-1\n";
        return 0;
    }
    cout << dp[n][0] << "\n";
}

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