Submission #1175078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175078		blueviolet	Robot (JOI21_ho_t4)	C++20	0 / 100	0 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, color, cost;
};

struct State {
    int node, cost;
    bool operator>(const State &other) const {
        return cost > other.cost;
    }
};

const int INF = 1e9;
int N, M;
vector<Edge> adj[1005];
map<int, vector<int>> color_adj[1005];

int dijkstra() {
    priority_queue<State, vector<State>, greater<State>> pq;
    vector<int> minCost(N + 1, INF);
    pq.push({1, 0});
    minCost[1] = 0;

    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        int u = cur.node, cur_cost = cur.cost;

        if (u == N) return cur_cost;

        for (auto &edge : adj[u]) {
            int v = edge.to, c = edge.color, p = edge.cost;

            if (color_adj[u][c].size() > 1) continue; // Ambiguous color

            if (cur_cost + p < minCost[v]) {
                minCost[v] = cur_cost + p;
                pq.push({v, minCost[v]});
            }
        }
    }

    return -1;
}

int main() {
    cin >> N >> M;
    vector<tuple<int, int, int, int>> edges;

    for (int i = 0; i < M; i++) {
        int A, B, C, P;
        cin >> A >> B >> C >> P;
        edges.push_back({A, B, C, P});
        adj[A].push_back({B, C, P});
        adj[B].push_back({A, C, P});
        color_adj[A][C].push_back(B);
        color_adj[B][C].push_back(A);
    }

    int result = dijkstra();
    cout << result << endl;
    return 0;
}

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