Submission #1229995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229995		phtung	Robot (JOI21_ho_t4)	C++20	34 / 100	102 ms	40176 KiB

Main

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

#define int long long


const int maxn = 1e5 + 5;
const int INF = 1e18;

struct EdgeInfo {
    int c, v, p;
};

vector<EdgeInfo> adj[maxn];
vector<pair<int, int>> g[maxn];
int dist[maxn];
bool visited[maxn];

void dijkstra(int total) {
    fill(dist, dist + total + 1, INF);
    dist[1] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!visited[v])
                    pq.push({dist[v], v});
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    int total = n;

    for (int i = 0; i < m; ++i) {
        int u, v, c, p;
        cin >> u >> v >> c >> p;
        adj[u].push_back({c, v, p});
        adj[v].push_back({c, u, p});
        g[u].push_back({v, p});
        g[v].push_back({u, p});
    }

    for (int u = 1; u <= n; ++u) {
        sort(adj[u].begin(), adj[u].end(), [](const EdgeInfo &a, const EdgeInfo &b) {
            return a.c < b.c;
        });

        int l = 0;
        for (int r = 1; r < adj[u].size(); ++r) {
            if (adj[u][r].c != adj[u][l].c) {
                if (r - l == 1) {
                    g[u].push_back({adj[u][l].v, 0});
                } else {
                    int sum = 0;
                    for (int k = l; k < r; ++k)
                        sum += adj[u][k].p;
                    ++total;
                    g[u].push_back({total, 0});
                    for (int k = l; k < r; ++k) {
                        int v = adj[u][k].v;
                        int p = adj[u][k].p;
                        g[v].push_back({total, 0});
                        g[total].push_back({v, sum - p});
                    }
                }
                l = r;
            }
        }

        int r = adj[u].size();
        if (r - l == 1) {
            g[u].push_back({adj[u][l].v, 0});
        } else {
            int sum = 0;
            for (int k = l; k < r; ++k)
                sum += adj[u][k].p;
            ++total;
            g[u].push_back({total, 0});
            for (int k = l; k < r; ++k) {
                int v = adj[u][k].v;
                int p = adj[u][k].p;
                g[v].push_back({total, 0});
                g[total].push_back({v, sum - p});
            }
        }
    }

    dijkstra(total);

    if (dist[n] < INF / 2) cout << dist[n] << '\n';
    else cout << -1 << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0; 
}

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