Submission #1192783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192783		vux2code	Robot (JOI21_ho_t4)	C++20	0 / 100	86 ms	23348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M), C(M);
    vector<ll> P(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> C[i] >> P[i];
        --A[i]; --B[i];
    }

    // Danh sách các cạnh theo đỉnh
    vector<vector<int>> inc(N);
    for (int i = 0; i < M; i++) {
        inc[A[i]].push_back(i);
        inc[B[i]].push_back(i);
    }

    // Xây danh sách cạnh có hướng với trọng số
    vector<vector<pair<int,ll>>> adj(N);
    // Xét từng đỉnh, nhóm các cạnh theo màu
    vector<int> tmp = { }; tmp.reserve(1000);
    for (int u = 0; u < N; u++) {
        auto &v = inc[u];
        // sort thứ tự theo màu
        sort(v.begin(), v.end(), [&](int i, int j) {
            return C[i] < C[j];
        });
        int L = v.size();
        int idx = 0;
        while (idx < L) {
            int j = idx;
            ll sumP = 0;
            // nhóm cùng màu C[v[idx]]
            while (j < L && C[v[j]] == C[v[idx]]) {
                sumP += P[v[j]];
                j++;
            }
            // với mỗi cạnh trong nhóm, tính trọng số hướng từ u
            for (int k = idx; k < j; k++) {
                int ei = v[k];
                // chi phí đổi tất cả cạnh còn lại trong nhóm:
                ll cost_conflict = sumP - P[ei];
                ll w = min(P[ei], cost_conflict);
                // xác định đỉnh kề
                int to = (A[ei] == u ? B[ei] : A[ei]);
                adj[u].emplace_back(to, w);
            }
            idx = j;
        }
    }

    // Dijkstra từ 0 đến N-1
    vector<ll> dist(N, INF);
    dist[0] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.emplace(0, 0);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        if (u == N-1) break;
        for (auto &e: adj[u]) {
            int v = e.first;
            ll w = e.second;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    if (dist[N-1] == INF) cout << -1;
    else cout << dist[N-1];
    cout << '\n';
    return 0;
}

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