Submission #388325

#	Time	Username	Problem	Language	Result	Execution time	Memory
388325		Kepha	Robot (JOI21_ho_t4)	C++11	100 / 100	1141 ms	79920 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<Edge> > adj[MX + 1];
map<int, ll> sum[MX + 1], dist2[MX + 1];
ll dist1[MX + 1];
priority_queue<Node> q;

int main() {
    // ifstream cin("tmp");

    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(Edge(c, b, d));
        adj[b][c].push_back(Edge(c, 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.price;
                if (cost + dist < dist1[edge.next]) {
                    dist1[edge.next] = cost + dist;
                    q.push(Node(cost + dist, 0, edge.next));
                }
            }
        }
        else {
            if (dist != dist1[cur]) continue;
            for (auto& c : adj[cur]) {
                for (auto& edge : c.second) {
                    ll cost1 = edge.price;
                    if (cost1 + dist < dist1[edge.next]) {
                        dist1[edge.next] = cost1 + dist;
                        q.push(Node(dist1[edge.next], 0, edge.next));
                    }

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

                    if (dist2[edge.next].count(edge.color) == 0
                        || dist < dist2[edge.next][edge.color]) {

                        dist2[edge.next][edge.color] = dist;
                        
                        q.push(Node(dist2[edge.next][edge.color], edge.color, edge.next));
                    }
                }
            }
        }
    }

    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