Submission #746216

#	Time	Username	Problem	Language	Result	Execution time	Memory
746216		stevancv	Robot (JOI21_ho_t4)	C++14	100 / 100	1109 ms	88236 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const ll linf = 1e18;
map<int, vector<array<int, 2>>> g[N];
map<int, ll> sum[N], dist[N];
int col[2 * N], cost[2 * N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v >> col[i] >> cost[i];
        g[u][col[i]].push_back({v, i});
        g[v][col[i]].push_back({u, i});
        dist[u][col[i]] = dist[v][col[i]] = linf;
        sum[u][col[i]] += cost[i];
        sum[v][col[i]] += cost[i];
    }
    for (int i = 2; i <= n; i++) dist[i][0] = linf;
    priority_queue<pair<ll, pair<int, int>>> pq;
    pq.push({0, {1, 0}});
    dist[1][0] = 0;
    while (!pq.empty()) {
        ll d = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
        if (d > dist[x][y]) continue;
        if (y > 0) {
            for (auto u : g[x][y]) {
                ll o = d + sum[x][y] - cost[u[1]];
                if (dist[u[0]][0] > o) {
                    dist[u[0]][0] = o;
                    pq.push({-o, {u[0], 0}});
                }
            }
            continue;
        }
        for (auto &uu : g[x]) {
            int y = uu.first;
            ll kk = sum[x][y];
            for (auto u : uu.second) {
                ll o = d + min((ll)cost[u[1]], kk - cost[u[1]]);
                if (dist[u[0]][0] > o) {
                    dist[u[0]][0] = o;
                    pq.push({-o, {u[0], 0}});
                }
                if (dist[u[0]][y] > d) {
                    dist[u[0]][y] = d;
                    pq.push({-d, {u[0], y}});
                }
            }
        }
    }
    if (dist[n][0] == linf) dist[n][0] = -1;
    cout << dist[n][0] << en;
    return 0;
}

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