Submission #388327

#	Time	Username	Problem	Language	Result	Execution time	Memory
388327		Kepha	Robot (JOI21_ho_t4)	C++11	100 / 100	1121 ms	79892 KiB

Main

// JOI 2021 Robot
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define MX 100000
using namespace std;
/*
struct Edge {
    int color, next;
    ll price;

    Edge (int _color = 0, int _next = 0, ll _price = 0) {
        color = _color, next = _next, price = _price;
    }
};
*/
struct Node {
    ll dist;
    int color, cur;

    Node (ll _dist = 0, int _color = 0, int _cur = 0) {
        dist = _dist, color = _color, cur = _cur;
    }

    bool operator<(const Node& x) const { return dist > x.dist; }
};

int N, M;
map<int, vector<pair<int, ll> > > adj[MX + 1];
map<int, ll> sum[MX + 1], dist2[MX + 1];
ll dist1[MX + 1];
priority_queue<Node> q;

int main() {
    cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        int a, b, c;
        ll d; 
        cin >> a >> b >> c >> d;

        adj[a][c].push_back({b, d});
        adj[b][c].push_back({a, d});   
        sum[a][c] += d;
        sum[b][c] += d;
    }

    fill(dist1 + 1, dist1 + 1 + N, INF);
    dist1[1] = 0;
    q.push(Node(0, 0, 1));

    while (q.size()) {
        int cur = q.top().cur, color = q.top().color;
        ll dist = q.top().dist;
        q.pop();
        
        if (color) {
            if (dist != dist2[cur][color]) continue;
            for (auto& edge : adj[cur][color]) {
                ll cost = sum[cur][color] - edge.second;
                if (cost + dist < dist1[edge.first]) {
                    dist1[edge.first] = cost + dist;
                    q.push(Node(cost + dist, 0, edge.first));
                }
            }
        }
        else {
            if (dist != dist1[cur]) continue;
            for (auto& c : adj[cur]) {
                for (auto& edge : c.second) {
                    ll cost1 = edge.second;
                    if (cost1 + dist < dist1[edge.first]) {
                        dist1[edge.first] = cost1 + dist;
                        q.push(Node(dist1[edge.first], 0, edge.first));
                    }

                    ll cost2 = sum[cur][c.first] - edge.second;
                    if (cost2 + dist < dist1[edge.first]) {
                        dist1[edge.first] = cost2 + dist;
                        q.push(Node(dist1[edge.first], 0, edge.first));
                    }

                    if (dist2[edge.first].count(c.first) == 0
                        || dist < dist2[edge.first][c.first]) {

                        dist2[edge.first][c.first] = dist;
                        
                        q.push(Node(dist2[edge.first][c.first], c.first, edge.first));
                    }
                }
            }
        }
    }

    if (dist1[N] >= INF) cout << "-1\n";
    else cout << dist1[N] << "\n";

    return 0;
}

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