Submission #1298194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298194		haithamcoder	Robot (JOI21_ho_t4)	C++20	0 / 100	337 ms	59360 KiB

Main

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

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

struct neighbour {
    ll v, c, p;
};

int main() {
    Algerian OI

    ll n, m;
    cin >> n >> m;

    vector<vector<neighbour>> adj(n);
    vector<map<ll, ll>> cnt(n), sum(n);
    vector<ll> dis(n);
    // vector<ll> c(m), p(m);

    for (ll i = 0; i < m; i++) {
        ll a, b, c, p;
        cin >> a >> b >> c >> p;
        --a; --b; --c;

        adj[a].push_back({b, c, p});
        adj[b].push_back({a, c, p});
        if (cnt[a][c] == 0) dis[a]++;
        if (cnt[b][c] == 0) dis[b]++;
        cnt[a][c]++;
        cnt[b][c]++;
        sum[a][c] += p;
        sum[b][c] += p;
    }

    for (ll i = 0; i < n; i++) {
        ll mn = inf;
        for (auto [col, s] : sum[i]) {
            mn = min(mn, s);
        }
        if (dis[i] < m) mn = 0;
        for (auto& [v, c, p] : adj[i]) {
            // if (dis[i] == m) {
            //     if (cnt[i][c] == 1) p = 0;
            //     else p = inf;
            // }
            // else if (cnt[i][c] == 1) p = 0;
            // if (cnt[i][c] == 1) p = 0;
            // else 
            p = min(p + mn, sum[i][c] - p);
        }
    }

    priority_queue<pll, vector<pll>, greater<>> pq;
    vector<ll> dist(n, inf);
    dist[0] = 0;
    pq.push({0, 0});

    while (pq.size()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;

        for (auto& [v, c, p] : adj[u]) {
            if (d + p < dist[v]) {
                dist[v] = d + p;
                pq.push({dist[v], v});
            }
        }
    }

    cout << (dist[n - 1] < inf ? dist[n - 1] : -1) << "\n";

    return 0;
}

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