Submission #1135409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135409		bozocode	Robot (JOI21_ho_t4)	C++20	100 / 100	406 ms	55616 KiB

Main

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

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int N, M; cin >> N >> M;
    vector<vector<array<int, 3>>> cross(N);
    vector<map<int, long>> sum(N), colcost(N);
    for (int i = 0; i < M; i++) {
        int u, v, c, p; cin >> u >> v >> c >> p; u--; v--;
        cross[u].push_back({v, c, p});
        cross[v].push_back({u, c, p});
        sum[u][c] += p;
        sum[v][c] += p;
    }
    vector<long> cost(N, 1e18);
    priority_queue<array<long, 2>> pq;
    pq.push({0, 0});
    vector<bool> visited(N);
    while (!pq.empty()) {
        auto [p, u] = pq.top(); p = -p;
        pq.pop();
        if (visited[u]) { continue; }
        visited[u] = true;
        cost[u] = p;
        for (auto [v, c, pp] : cross[u]) {
            if (colcost[v].find(c) == colcost[v].end()) { colcost[v][c] = p; }
            long best = p;
            auto it = colcost[u].find(c);
            if (it != colcost[u].end()) { best = (*it).second; }
            pq.push({-min(best + sum[u][c] - pp, p + pp), v});
        }
    }
    if (!visited[N - 1]) { cout << -1 << "\n"; }
    else { cout << cost[N - 1] << "\n"; }
}

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