Submission #718738

#	Time	Username	Problem	Language	Result	Execution time	Memory
718738		tcmmichaelb139	Robot (JOI21_ho_t4)	C++17	0 / 100	3078 ms	49416 KiB

Main

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

const int MAXN = 100001;

long long dist[MAXN][2];

struct node {
    int v;
    long long c;
    int p;
    bool chgd;
    bool operator<(const node &rhs) const {
        return dist[v][chgd] > dist[rhs.v][rhs.chgd];
    }
};

int n, m;
vector<pair<int, pair<int, long long>>> adj[MAXN];
int vis[MAXN][2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        long long d;
        cin >> a >> b >> c >> d;
        adj[a].push_back({b, {c, d}});
        adj[b].push_back({a, {c, d}});
    }

    for (int i = 0; i <= n; i++)
        dist[i][0] = dist[i][1] = 1e18;
    dist[1][0] = 0;

    priority_queue<node> q;
    q.push({1, 0, -1, 0});
    while (!q.empty()) {
        node v = q.top();
        q.pop();

        if (vis[v.v][v.chgd]) {
            map<int, long long> cols;

            for (auto u : adj[v.v]) {
                if (!v.chgd || u.first != v.p)
                    cols[u.second.first] += u.second.second;
                if (vis[u.first][1]) continue;
                dist[u.first][1] = min(dist[u.first][1], v.c + u.second.second);
            }

            for (auto u : adj[v.v]) {
                if (vis[u.first][0]) continue;
                dist[u.first][0] = min(dist[u.first][0], v.c + cols[u.second.first] - u.second.second);
            }
            continue;
        }
        vis[v.v][v.chgd] = true;

        map<int, long long> cols;

        for (auto u : adj[v.v]) {
            if (!v.chgd || u.first != v.p)
                cols[u.second.first] += u.second.second;
            if (vis[u.first][1]) continue;
            dist[u.first][1] = min(dist[u.first][1], dist[v.v][v.chgd] + u.second.second);
            q.push({u.first, dist[v.v][v.chgd] + u.second.second, v.v, true});
        }

        for (auto u : adj[v.v]) {
            if (vis[u.first][0]) continue;
            dist[u.first][0] = min(dist[u.first][0], dist[v.v][v.chgd] + cols[u.second.first] - u.second.second);
            q.push({u.first, dist[v.v][v.chgd] + cols[u.second.first] - u.second.second, v.v, false});
        }
    }
    cout << min(dist[n][0], dist[n][1]) << '\n';
}

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